58
\$\begingroup\$

An integer is binary-heavy if its binary representation contains more 1s than 0s while ignoring leading zeroes. For example 1 is binary-heavy, as its binary representation is simply 1, however 4 is not binary heavy, as its binary representation is 100. In the event of a tie (for example 2, with a binary representation of 10), the number is not considered binary-heavy.

Given a positive integer as input, output a truthy value if it is binary-heavy, and a falsey value if it is not.

Testcases

Format: input -> binary -> output

1          ->                                1 -> True
2          ->                               10 -> False
4          ->                              100 -> False
5          ->                              101 -> True
60         ->                           111100 -> True
316        ->                        100111100 -> True
632        ->                       1001111000 -> False
2147483647 ->  1111111111111111111111111111111 -> True
2147483648 -> 10000000000000000000000000000000 -> False

Scoring

This is so fewest bytes in each language wins

\$\endgroup\$
  • \$\begingroup\$ What if my language can't handle the last test case because it's outside the bounds of what's considered a positive integer? \$\endgroup\$ – musicman523 Jul 13 '17 at 14:52
  • 1
    \$\begingroup\$ @musicman523 afaik Standard I/O rules state that you only have to accept numbers representable by your language's number format. Note that "gaming" this by using something like boolfuck is considered a Standard Loophole \$\endgroup\$ – Skidsdev Jul 13 '17 at 14:53
  • \$\begingroup\$ Does any truthy/falsy value count or do we need two distinct values? \$\endgroup\$ – Erik the Outgolfer Jul 13 '17 at 15:22
  • \$\begingroup\$ @EriktheOutgolfer any value \$\endgroup\$ – Skidsdev Jul 13 '17 at 15:35
  • 6
    \$\begingroup\$ Aka A072600, if this helps anybody. \$\endgroup\$ – dcsohl Jul 13 '17 at 17:59

77 Answers 77

2
\$\begingroup\$

Ruby, 39 bytes

->n{b=n.to_s 2;b.count(?1)>b.count(?0)}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You only need check that the 1-count is more than half, so ->n{b=n.to_s 2;b.count(?1)>b.size/2} is 3 bytes shorter. \$\endgroup\$ – Chowlett Jul 17 '17 at 12:36
2
\$\begingroup\$

R, 74 62 bytes

x=scan();n=strtoi(intToBits(x)[0:log2(x)+1]);2*sum(n)>sum(n|T)

Edit:

Thanks Giuseppe! -12 bytes

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Let's see...you can use strtoi instead of as.logical and instead of length(n) you can use sum(n|T) and then obviously you want 2*sum(n)>length(n), aaand you can use x=scan() instead of a function definition (I did the same!); those are just handy R golfing tips :) \$\endgroup\$ – Giuseppe Jul 13 '17 at 20:45
  • \$\begingroup\$ @Giuseppe Very neat shortcut with sum(n|T). Thanks! \$\endgroup\$ – Maxim Mikhaylov Jul 13 '17 at 21:51
2
\$\begingroup\$

TIS-100, 432 Bytes

105502 Cycles, 6 Nodes, 46 Instructions

@1
MOV RIGHT NIL
MOV UP DOWN
@2
MOV DOWN LEFT
@5
S:MOV ANY ACC
L:SUB 2
SWP
ADD 1
SWP
JGZ L
JLZ B
MOV 0 DOWN
A:MOV 0 ACC
SWP
SUB DOWN
MOV ACC RIGHT
JMP S
B:MOV 1 DOWN
JMP A
@6
MOV 0 UP
L:MOV LEFT ACC
SUB 1
JEZ B
ADD 1
MOV ACC LEFT
MOV 0 DOWN
JMP L
B:MOV 0 UP
MOV 1 DOWN
JMP L
@9
S:MOV UP ACC
MOV ACC UP
JEZ B
MOV 1 RIGHT
JMP S
B:MOV -1 RIGHT
@10
L:SWP
ADD LEFT
SWP
MOV UP ACC
JEZ L
SWP
JGZ B
MOV 0 DOWN
JMP K
B:MOV 1 DOWN
K:MOV 0 ACC

EDIT: Explained:

@5 receives any value and divides by two. It passes the remainder down and the quotient right, making sure to correct any errors by subtracting the remainder from @9. @6 receives quotients from @5. If the quotient is 1, it terminates the loop by passing a signal down to print out the answer, then passing a signal to @1 via @2 to read in the next value. Speaking of, @9 and @10 hold the greater than/less than state of 1s and 0s by adding 1 for each 1 and -1 for each 0, then jumping based on the sum.

Play the level by pasting this into the game.

function get_name()
    return "BINARY COLLAPSER"
end

function get_description() return { "WRITE 1 TO OUT IF THE BINARY REPRESENTATION OF IN CONTAINS MORE ONES THAN ZEROES", "WRITE 0 TO OUT OTHERWISE", "IGNORE LEADING ZEROES"} end

function get_streams() input = {} output = {} for i = 1,39 do x = math.random(1, 999) input[i] = x ones = 0 zeroes = 0 while (x>0) do if (x%2 == 1) then ones = ones + 1 x = x - 1 else zeroes = zeroes + 1 end x = x/2 end if (ones > zeroes) then output[i] = 1 else output[i] = 0 end end return { { STREAM_INPUT, "IN.A", 1, input }, { STREAM_OUTPUT, "OUT.A", 2, output }, } end

function get_layout() return { TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, TILE_COMPUTE, } end

\$\endgroup\$
  • \$\begingroup\$ You can now try it online! (Though, it seems this solution gets stuck when 1 is given as input.) \$\endgroup\$ – Phlarx May 2 '18 at 20:38
2
\$\begingroup\$

Common Lisp, 49 48 bytes

(lambda(x)(>(logcount x)(/(integer-length x)2)))

Try it online!

-1 byte thanks to ceilingcat!

Only two builtin functions (and two operators), but with the long names typical of Common Lisp! At least conceptually very simple.

\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 43 bytes

n->n.bitCount(n)>n.toString(n,2).length()/2

Try it online!

Java (OpenJDK 8), 31 bytes using BigInteger

I suspect this would need to count the import for 28 more bytes though.

n->n.bitCount()>n.bitLength()/2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Didn't even knew about bitCount. Nice answer! I had something like this in my mind: n->{String s=n.toString(n,2);return s.replace("0","").length()>s.length()/2;} \$\endgroup\$ – Kevin Cruijssen Jul 14 '17 at 7:57
  • \$\begingroup\$ @KevinCruijssen If you want to try another Java solution, I'd suggest a loop with n/=2 and n%2>0?i++:i--. Might be shorter; at least close. \$\endgroup\$ – JollyJoker Jul 14 '17 at 8:26
  • \$\begingroup\$ It would be simple to use numberOfLeadingZeros to get the length, but the method name is 20 letters long :( \$\endgroup\$ – JollyJoker Jul 14 '17 at 13:29
  • \$\begingroup\$ If you use Java 9's JShell you don't need the import since java.math.* is imported implicitly. \$\endgroup\$ – David Conrad Aug 3 '17 at 15:13
  • \$\begingroup\$ @DavidConrad Thanks, it seems to have a usefult list of default imports for golfing \$\endgroup\$ – JollyJoker Aug 4 '17 at 7:28
2
\$\begingroup\$

Japt, 9 bytes

0<¢¬x®r0J

Try it online!

Explanation:

0<¢¬x®r0J
  ¢        // Binary; Base-2 of the input
   ¬       // Split into an array
     ®     // Map; At each item:
      r0J  //   Replace 0 with -1
    x      // Sum;
0<         // If the result is greater-than 0, return true; Else, false;
\$\endgroup\$
2
\$\begingroup\$

k, 22 bytes

{.5<avg X@&:|\X:0b\:x}

q translation:

{.5 < avg X where maxs X:0b vs x}

Interpreter available here

\$\endgroup\$
2
\$\begingroup\$

Python, 33 bytes

lambda x:2*x<4**bin(x).count('1')

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 4 bytes

Returns 1 if binary heavy, 0 otherwise

b.MW

Try it online!

b            Convert to binary
 .M          Push a list of most frequent chars (contains 0 and 1 in case of a tie)
   W         Push the lowest value from the list
             Implicit output
\$\endgroup\$
2
\$\begingroup\$

Excel, 88 bytes

Un-golfed answer that only handles values up to 511.

=SUMPRODUCT(--MID(DEC2BIN(A1),ROW(OFFSET(A$1,,,LEN(DEC2BIN(A1)))),1))>LEN(DEC2BIN(A1))/2

Excel & CSV, 75 bytes.

Save as CSV, and insert Input before first comma:

,=DEC2BIN(A1),=SUMPRODUCT(--MID(B1,ROW(OFFSET(A$1,,,LEN(B1))),1))>LEN(B1)/2
\$\endgroup\$
2
\$\begingroup\$

tinylisp, 93 bytes

(d _(q((N R D)(i(l N 2)(i R(_ R 0(a(s(s 1 N)N)D))(l D 1))(_(s N 2)(a R 1)D
(d H(q((N)(_ N 0 0

This was fun. I went through a few different ideas before I was able to beat my initial 105-byte solution that used library functions.

Try it online!

Ungolfed + explanation

(load library)

(def _binary-heavy
 (lambda (num rest diff)
  (if (less? num 2)
   (if rest
    (_binary-heavy rest 0 (+ diff (if num (neg 1) 1)))
    (less? diff 1))
   (_binary-heavy (- num 2) (inc rest) diff))))

(def binary-heavy (lambda (num) (_binary-heavy num 0 0)))

There are no division or modulo builtins in tinylisp, so we use an algorithm that only does addition and subtraction.

The helper function _binary-heavy has three arguments:

  • num starts out as the integer we're analyzing
  • rest ends up as half of num, and then becomes the new num in a recursive call
  • diff stores the difference between the number of 0 bits and the number of 1 bits we've seen so far

The function recurses in a couple of different ways:

  • If num is 2 or greater, subtract 2 from num, add 1 to rest, and recurse.
  • If num is 0 or 1, then rest now contains the original num divided by 2, and num contains the original num mod 2. In other words, num is the least significant bit, and rest is the rest of the number. Here we have two possibilities:
    • If rest is not zero, there are more bits to process, so we update diff and recurse with rest as the new num. Since diff is (number of 0 bits) minus (number of 1 bits), we want to add 1 if num is 0 and -1 if num is 1. The golfed code accomplishes this by adding (s(s 1 N)N)--in infix, 1 - 2*num.
    • If rest is zero, we're done and just need to return a result. Note that num now holds the most significant bit, which is always 1. So the final diff is diff - 1, and we want to check whether this is less than 0. But diff - 1 < 0 is the same as diff < 1, which is what we return.

Finally, we define our main function, binary-heavy, to take one argument num and pass it on to the helper function, with rest and diff initially 0.

\$\endgroup\$
2
\$\begingroup\$

q/kdb+, 34 33 28 bytes

Solution:

sum[b]>.5*(#)*:[b&:]_b:2 vs 

Examples:

q)sum[b]>.5*(#)*:[b&:]_b:2 vs 1
1b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 2
0b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 4
0b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 5
1b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 60
1b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 316
1b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 632
0b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 2147483647
1b
q)sum[b]>.5*(#)*:[b&:]_b:2 vs 2147483648
0b

Explanation:

Convert input to binary, chop off leading zeroes, compare whether there are more ones (sum[b]) than half the length of the list (0.5 * count...).

sum[b] > 0.5 * count first[where b] _ b:2 vs / ungolfed solution
                                        2 vs / convert right to base 2
                                      b:     / save in variable b for use later
                           where b           / indexes where b is true
                     first[       ]          / perform first on the stuff in brackets
                                    _        / drop, drops left items from right, basically drop all leading 0s
               count                         / returns length of this list
         0.5 *                               / half this value
       >                                     / greater-than, returns true or false
sum[b]                                       / how many 1s there are in b

Notes:

Golfing was simply replacing the q keywords with their k equivalents

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 6 bytes

-2 bytes thanks to Erik the Outgolfer

b1Ý¢`‹

Try it online! or Try all tests

\$\endgroup\$
  • \$\begingroup\$ b{γ€g¥ is what I've tied you with ;). \$\endgroup\$ – Magic Octopus Urn Jul 17 '17 at 22:41
1
\$\begingroup\$

Pari/GP, 27 bytes

n->2*vecsum(b=binary(n))>#b

Try it online!

\$\endgroup\$
1
\$\begingroup\$

GolfScript, 15 bytes

~2base.0-,\1-,>

Try it online!

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 72 bytes

([convert]::ToString("$args",2)-replace'1','+1'-replace'0','-1'|iex)-gt0

Try it online!

Converts to Base 2, changes 100 to +1-1-1 and eval, checks if the result ends up >0.

\$\endgroup\$
1
\$\begingroup\$

Stacked, 17 bytes

[bits tmo sum 0>]

Try it online!

This is a pretty simple answer. Takes the bits of the top number, perofrms 2n-1 (tmo), calculates their sum, and checks if it is > than 0.

\$\endgroup\$
1
\$\begingroup\$

TI-Basic, 29 bytes

:Prompt N
:While int(N
:.5int(N→N
:P-1+4fPart(N→P
:End
:P>0
\$\endgroup\$
1
\$\begingroup\$

CJam, 10 bytes

qi2b$_:!$>

Try it online

qi2b   e# convert input to base 2 as an array (43 => [1,0,1,0,1,1,])
$      e# sort array ([0,0,1,1,1,1])
_:!    e# make copy of array and invert truth value of each element ([1,1,0,0,0,0])
$      e# sort copy ([0,0,0,0,1,1])
>      e# if first array is lexicographically greater than copy, return true (only happens if 1st array had more ones than zeroes).
\$\endgroup\$
1
\$\begingroup\$

Rust, 30 bytes

|x:u64|x<1<<2*x.count_ones()-1

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Sed, 218 bytes (91 with unary input)

:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu
s/$/x/
:a
s/;;/,/g
s/,x/,x0/
s/;x/x1/
y/,/;/
s/10//
s/01//
ta
s/x$/0/
s/\(.\)\1/\1/g
s/x//

Outputs 1 for truthy and 0 for falsey.

Decimal to unary conversion from this answer.

\$\endgroup\$
  • \$\begingroup\$ You can use the -r flag in GNU sed to avoid escaping parentheses. Also you can use unnamed labels (empty label) instead of the u label to save two further bytes. Also, s/10//;s/01// can become s/10|01//. \$\endgroup\$ – Kritixi Lithos Jul 15 '17 at 8:47
1
\$\begingroup\$

05AB1E, 6 bytes

b{γ€g¥

Try it online!

Results:

  • 0 or higher means a non-heavy number.
  • Negative numbers represent the binary-heavy numbers.
\$\endgroup\$
1
\$\begingroup\$

Attache, 13 bytes

{1~_>0~_}@Bin

Try it online!

Explanation

{1~_>0~_}@Bin
          Bin    convert the input to binary
{       }@       _ = binary input
 1~_             count of 1s in input
    >            is greater than?
     0~_         the count of 0s in the input

Alternatives

17 bytes: Min@Commonest@Bin

17 bytes: /N@@Commonest@Bin

18 bytes: {Sum@_/#_>0.5}@Bin

18 bytes: /Id@@Commonest@Bin

18 bytes: Last@Commonest@Bin

19 bytes: {_>0.5}@Average@Bin

22 bytes: 0&`<@Sum##{2*_-1}=>Bin

23 bytes: `<@@{Sum@`=&_=>0'1}@Bin

23 bytes: {&`<!Sum@`=&_=>0'1}@Bin

30 bytes: {&`<!Sum=>Table[`=,0'1,_]}@Bin

\$\endgroup\$
1
\$\begingroup\$

Forth (gforth), 56 bytes

: f 0 swap begin 2 /mod >r 2* 1- + r> ?dup 0= until 0> ;

Try it online!

Explanation

Loop through the binary digits of the number and add 1 to a counter if the digit is 1, and subtract 1 if the digit is 0. If the total is greater than 0 there are more 1's than 0's.

Code Explanation

: f            \ start new word definition
  0 swap       \ add a counter and move it below the input number on the stack
  begin        \ start an uncounted loop
    2 /mod     \ get the quotient and remainder of dividing by 2 (get binary digit and rest of number)
    >r         \ stick the remaining number on the return stack
    2* 1- +    \ convert remainder to 1 or -1 and add to counter
    r>         \ remove remaining number from the return stack
    ?dup       \ duplicate if not equal to 0
  0= until     \ end the loop if the remaining number is 0
  0>           \ return true if counter is greater than 0
;              end word definition  
\$\endgroup\$
1
\$\begingroup\$

Ruby, 30 27 bytes

->n{n<4**n.digits(2).sum/2}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Alchemist, 122 bytes

_->In_a
n+a+0z->n+z
a+z->b
n+0a->d
0n+z->2c
0n+0z+b->a
0n+0z+0b+a->a+n
c+d->
0z+0a+0b+0_+0f->s+f
0c+s->Out_c
0d+c+s->Out_f

Try it online!

Test cases

Outputs 0 for false and 1 for true.

\$\endgroup\$
0
\$\begingroup\$

CJam, 11 bytes

2,ri2bfe=:<

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @MartinEnder How does :< work in your example? If it's a quick fold or quick map, I don't really get it. \$\endgroup\$ – geokavel Jul 14 '17 at 2:46
  • \$\begingroup\$ @geokavel I just noticed it doesn't work when the input contains only 0-bits or only 1-bits so nevermind. \$\endgroup\$ – Martin Ender Jul 14 '17 at 4:59
  • \$\begingroup\$ @EriktheOutgolfer I suggested sorting, RLE, comparison, but that assumes that both zero and one are present in the number. \$\endgroup\$ – Martin Ender Jul 14 '17 at 9:12
  • \$\begingroup\$ @MartinEnder Oh yeah RLE is a big no here. I think you suggested ri2b$e`0f=:< which is longer anyways. \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 9:13
0
\$\begingroup\$

Pyth, 15 bytes

<.*uXsHG1.BQ,ZZ

Try it online! Probably not the shortest solution out there, but I find it elegant.

Explanation

         .BQ       # Convert input to a binary string
   u        ,ZZ    # Reduce starting with (0, 0)...
    XsHG1          # ...by adding 1 to the first element of the couple if a 0 is encountered, or to the second element if a 1 is encountered
 .*                # Splat the couple: (x, y) -> x y
<                  # Check that x < y (x being the number of zeros, y the number of ones)
\$\endgroup\$
  • \$\begingroup\$ Probably? \$\endgroup\$ – Erik the Outgolfer Jul 13 '17 at 15:25
  • 3
    \$\begingroup\$ @EriktheOutgolfer At least mine has an explanation. \$\endgroup\$ – Jim Jul 13 '17 at 15:32
0
\$\begingroup\$

Check, 45 41 bytes

>\          #v
#:>2%R+r\)\$##?
d$R-)>]*!p

Try it online!

This is probably golfable. I don't like the huge space on the first line.

Explanation

The program starts out with the input number on top of the stack. The IP is in 1D mode.

The > pushes a 0 to the stack, and then the \ swaps it with the input number. The stack now looks like 0, input, and the register is initialized to 0.

#v turns the IP into 2D mode and makes it start moving downwards. The second line is a loop that does this:

  • If the current value is 0, end the loop.
  • Otherwise, take the current value modulo 2.
  • Add that value to the value of the register (which counts the number of ones), and then unconditionally add 1 to the other value on the stack (which counts the total number of digits).
  • Int-divide the current value by 2.

Once the loop exits, one value on the stack will contain the number of digits. Divide that by 2. Then, take the value in the register, which counts the total number of ones. If the number of ones is greater than the total number of digits // 2, then the condition is true. However, Check has no built-in for checking whether one number is greater than another, so this is the simplest way:

  • Subtract the two values. The condition is now only true when the result is negative.
  • Increment the value. The condition is now only true when the result is negative or 0.
  • Repeat a singleton array that many times. In Check, trying to repeat an array a negative amount of times yields an empty array, which means that the result will be an empty array if and only if the condition is true.
  • The !p negates the empty array and prints the result.
\$\endgroup\$
0
\$\begingroup\$

Ohm, 7 bytes

bS╞╠l;h

Explanation

bS╞╠l;h  Main wire
b        binary representation
 S       sorted
  ╞      grouped
   ╠l;   sorted by length
       h the first element
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.