62
\$\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\$
8
  • \$\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
  • 7
    \$\begingroup\$ Aka A072600, if this helps anybody. \$\endgroup\$ – dcsohl Jul 13 '17 at 17:59

81 Answers 81

2
\$\begingroup\$

Ruby, 39 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\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\$

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\$
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\$
2
  • 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\$
1
  • \$\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\$
0
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\$
5
  • \$\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\$
2
\$\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\$
2
+100
\$\begingroup\$

APL (Dyalog Unicode), 14 bytes

-6 thanks to @Razetime -1 thanks to @rak1507

f←(≢<2×+/)2∘⊥⍣¯1

explanation:

(≢<2×+/)2∘⊥⍣¯1
        2∘⊥⍣¯1     ⍝ convert the number to a binary vector inverting decode (⊥)
   2×+/            ⍝ doubled count of ones in the binary representation
 ≢                 ⍝ amount of bits in the binary representation
  <                ⍝ is it smaller?

Try it online!

original solution:

(+/∘~<+/)2∘⊥⍣¯1

explanation:

(+/∘~<+/)2∘⊥⍣¯1
         2∘⊥⍣¯1     ⍝ convert the number to a binary vector inverting decode (⊥)
      +/            ⍝ count of ones in the binary representation
    ~               ⍝ negate the number
 +/∘                ⍝ count ones in the negated number, effectively counting zeros
     <              ⍝ is the amount of zeros smaller than the amount of ones?
\$\endgroup\$
1
  • \$\begingroup\$ -6 \$\endgroup\$ – Razetime Dec 20 '20 at 12:10
1
\$\begingroup\$

05AB1E, 8 6 bytes

-2 bytes thanks to Erik the Outgolfer

b1Ý¢`‹

Try it online! or Try all tests

\$\endgroup\$
1
  • \$\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\$

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\$
1
  • \$\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\$ – user41805 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\$

Stax, 4 bytes

:B:M

Run and debug it

:B gets the binary digits of the input. :M gets the mode. In the case of a tie, it will be the last element to appear (always 0).

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

K (ngn/k), 17 13 10 bytes

-4 bytes by changing approach

-3 bytes by making code tacit (thanks @ngn)

0>+/1-2*2\

Try it online!

  • 2\x convert input to base-2; this already trims any leading 0's
  • 1-2* convert 1's to -1's and 0's to 1's
  • 0>+/ is the sum less than 0?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ { x} can be removed \$\endgroup\$ – ngn Dec 26 '20 at 22:28
  • \$\begingroup\$ D'oh, good catch! \$\endgroup\$ – coltim Dec 26 '20 at 22:33
0
\$\begingroup\$

CJam, 11 bytes

2,ri2bfe=:<

Try it online!

\$\endgroup\$
4
  • \$\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

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.