# Is the number binary-heavy?

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

• What if my language can't handle the last test case because it's outside the bounds of what's considered a positive integer? Jul 13, 2017 at 14:52
• @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 Jul 13, 2017 at 14:53
• Does any truthy/falsy value count or do we need two distinct values? Jul 13, 2017 at 15:22
• @EriktheOutgolfer any value Jul 13, 2017 at 15:35
• Aka A072600, if this helps anybody. Jul 13, 2017 at 17:59

# 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

# Red, 74 bytes

func[n][(sum b: collect[until[keep n % 2 1 > n: n / 2]])>((length? b)/ 2)]


Try it online!

# 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


# C, 49 bytes

f(n){int a=0;for(;n;n/=2)a+=n%2?1:-1;return a>0;}


Possible too much long for you...

• Could you specify the compiler you used? Feb 6, 2019 at 10:23
• Possibly f(n,a){for(a=0;n;n/=2)a+=n%2*2-1;a=a>0;}? Feb 6, 2019 at 10:25
• @JonathanFrech each C compiler
– user58988
Feb 6, 2019 at 12:24
• I would think there are a lot of C compilers out there. Do you mean C89 compliant or something along those lines? Feb 6, 2019 at 19:39
• Yes C89 standard (I hope at last)... It would be good for me to know some C compiler not compile above code
– user58988
Feb 7, 2019 at 10:10

# 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).

## ARM Thumb-2 (alternative), 16 bytes

Alternative approach which mirrors this x86 answer although it is just as small to maintain the bool return value.

Since we need to mov the result to r0 anyways, we can invert the operation and use that opcode to return the sign bit.

Raw machine code:

2100 0840 bf2c 3901 3101 d1fa 0fc8 4770


Uncommented Assembly:

        .syntax unified
.arch armv6t2
.globl binary_heavy
.thumb
.thumb_func
binary_heavy:
movs    r1, #0
.Lloop:
lsrs    r0, r0, #1
ite     cs
subcs   r1, #1
bne     .Lloop
.Lloop_end:
lsrs    r0, r1, #31
bx      lr


The explanation is the same as the original one, but instead of adding to two different variables, we are adding and subtracting from the same variable, and returning the sign bit by doing a logical right shift by 31.

## ARM Thumb-2 (previous approach), 22 20 bytes

Longer but uses an original idea.

Raw machine code:

2101 2200 0840 bf2c 3201 3101 d1fa 428a
4140 4770


Uncommented Assembly:

        .syntax unified
.arch armv6t2
.globl binary_heavy
.thumb
.thumb_func
binary_heavy:
movs    r1, #1
movs    r2, #0
.Lloop:
lsrs    r0, r0, #1
ite     cs
bne     .Lloop
.Lloop_end:
cmp     r2, r1
bx      lr


## Explanation

We are about to do some wonky stuff with the condition codes, so you might want to look at the condition code table in this article if you aren't familiar with them.

C signature:

bool binary_heavy(uint32_t val);


First, set up r1 to count the zeros and r2 to count the ones.

binary_heavy:
movs    r1, #1
movs    r2, #0


Then, begin our loop. All the logic can be handled by how lsrs updates the flags.

lsrs does a logical right shift, stores the last bit shifted in the carry flag, and sets the zero and negative flags based on the result.

So we can basically do this logic using nothing but lsrs and some flag checking:

do {
if (val & 1) {
++ones;
} else {
++zeros;
}
} while (val >>= 1);

.Lloop:
lsrs    r0, r0, #1


First, we do an IT block to add to either the ones count or the zeroes count.

        ite     cs


Thankfully, since most narrow instructions do not set flags in IT blocks, we can also use the same lsrs flags to check if the value is still non-zero and loop.

        bne     .Lloop


Here is why we set the zeros counter to 1.

We can do a shortcut if we can turn the condition into a greater than or equal. However, if the ones and zeros are equal, it is considered not binary heavy. That is why we need to start the zeros with 1, because we can offset it.

The shortcut? You guessed it, an add with carry!

• We know that r0 is zero since if it wasn't, we'd be looping now.
• That means that r0 will be 0 + 0 + carry.
• Greater than or equal means the carry flag is set
• Therefore, the carry flag being set means greater than or equal.
• Since we modified the zeros initial value, greater than or equal means that the number is binary heavy.
• Which means the carry flag is set if the number is binary heavy.

So we are essentially setting r0 to the carry flag, making it act as a boolean....and our return value.

.Lloop_end:
cmp     r2, r1


Return.

        bx    lr


# K (ngn/k), 1713 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?
• { x} can be removed
– ngn
Dec 26, 2020 at 22:28
• D'oh, good catch! Dec 26, 2020 at 22:33

# Husk, 4 bytes

>.Aḋ


Try it online!

>.Aḋ
A   # The average
ḋ  # of the binary digits
>     # is greater than
.    # 0.5


# K (ngn/k), 19 bytes

{n:2\x;(#n^1)<#n^0}


Try it online!

This is the first time where using a variable saves more bytes than just duplicate. It's also much simpler than I thought. Return 1 for true, and 0 for false.

Explanation:

{n:2\x;(#n^1)<#n^0}    Main function. Takes x as input
n:                    Assign variable n to
2\x;                x converted to base 2, return back a binary array
(#   )          Length of
n^1           n without 1 in its array
<         Less than
#        Length of
n^0     n without 0 in its array


# J-uby, 49 32 bytes

Based on G B’s Ruby answer.

:<%(~:digits&2|:sum|:**&4|~:/&2)


Attempt This Online!

# ///, 156 bytes

/9/8*//8/7*//7/6*//6/5*//5/4*//4/3*//3/2*//2/1*//1/0*//*0/9*//0///*/>oi//i>/i//io/oi//oii/i\o//oi/_i//_///>o/>//>///i\o///o\i///|i/T//Ti/T//|o/F//Fo/F//|/F/


Try it online!

The input is |n where n is a number.

## Explanation:

/9/8*//8/7*//7/6*//6/5*//5/4*//4/3*//3/2*//2/1*//1/0*//*0/9*//0//


Convert from Base 10 (decimal) to unary (Taken from the wiki)

/*/>oi//i>/i//io/oi//oii/i\o//oi/_i//_///>o/>//>//


Convert from unary to binary (i and o) (Also, taken from the wiki)

/i\o///o\i//


Replace io to empty string as many times, then repeat but oi to empty string

/|i/T//Ti/T/


If the new string has i, Replace to T

/|o/F//Fo/F/


Else, if the new string has o, Replace to F

/|/F/


Else replace to F

And output the new string.

# Jelly, 4 bytes

BÆṃP


Try it online!

Nothing clever here :P

   P    Take the product of
Æṃ     the most common
B       binary digits.


# Thunno, $$\8\log_{256}(96)\approx\$$ 6.58 bytes

bD1cs0c>


Attempt This Online!

#### Explanation

   # Implicit input
bD # Binary, duplicate
1c # Count of 1s
s  # Swap
0c # Count of 0s
>  # Greater than?
# Implicit output


# Turing Machine Code, 332 bytes

Terminates in state halt for truthy, or halt-r for falsey.

0 * * r 0
0 _ _ l 1
1 0 9 l 1
1 9 8 l 2
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 _ _ l A
2 _ _ l 3
2 * * l 2
3 1 0 l 3
3 * 1 r 4
4 * * r 4
4 _ _ r 0
A * * l A
A 1 & l B
A 0 & l C
A & & l A
B 0 & r D
B * * l B
C 1 & r D
C * * l C
D * * r D
D _ _ l A
B _ _ * halt
C _ _ * halt-r
A _ _ * halt-r


# Go, 101 bytes

import(."strconv";."strings")
func f(n int64)bool{x:=FormatInt(n,2)
return Count(x,"1")>Count(x,"0")}


Attempt This Online!

#### Commented

import (."strconv"; ."strings")        // Boilerplate
func f(n int64) bool {                 // Boilerplate
x := FormatInt(n, 2)                   // Convert n to binary
return Count(x, "1") > Count(x, "0")}  // Is the count of 1s more than the count of 0s?


# Thunno 2, 6 bytes

ḃk#cẸ<


Attempt This Online!

#### Explanation

ḃk#cẸ<  # Implicit input           -> n
ḃ       # Binary representation    -> binary
k#     # Push the pair [0, 1]     -> binary, [0, 1]
c    # Counts of each           -> [count of 0, count of 1]
Ẹ   # Dump onto stack          -> count of 0, count of 1
<  # Less than                -> count of 0 < count of 1
# Implicit output


# JavaScript (Node.js), 44 47 bytes

-3 bytes thanks to l4m2 tip and some other improvements

Different approach but can't beat the recursive JS answers.

l=>[...l.toString(a=2)].map(e=>a+=e-.5)&&a>2


Try it online!

The algorithm is pretty straightforward.
We convert the decimal into binary, and then we parse each bit while maintaining a score. For each 1 we increase the score by 0.5, and for each 0 we decrease it by 0.5.
At the end we check if the score is greater than 2 (because it was shorter that way for the declaration of variable a)

• e*2-1 => e-.5
– l4m2
Oct 12 at 3:51
• @l4m2 Thanks for the tip! It's simple but for some reason i didn't think of it. I updated my solution Oct 19 at 9:55

# Uiua, 7 bytes

>∩/+¬.⋯


Try it!

      ⋯     # encode as bits
¬.      # make a copy with bitwise-NOT
∩          # for each of these:
/+        #   sum
>           # is the second bigger than the first?


# Fortran (GFortran), 38 bytes body, 13 bytes boilerplate

program x

end


Try it online: 1, 2, 4, 5, 60, 316, 632, 2147483647, 2147483648

The code reads a single 64 bit integer n from standard input and ouputs T for a binary-heavy number or F otherwise.

It uses popcnt() to count the number of ones and leadz() to count the number of leading zeros, both in the binary representation of n. The inequality to check is

popcnt(n) > (64 - leadz(n) - popcnt(n))


which can be written shorter as

(2 * popcnt(n)) > (64 - leadz(n))


The code needs to be compiled with -fdefault-integer-8 to enable 64 bit integers as the default.

# CJam, 11 bytes

2,ri2bfe=:<


Try it online!

• @MartinEnder How does :< work in your example? If it's a quick fold or quick map, I don't really get it. Jul 14, 2017 at 2:46
• @geokavel I just noticed it doesn't work when the input contains only 0-bits or only 1-bits so nevermind. Jul 14, 2017 at 4:59
• @EriktheOutgolfer I suggested sorting, RLE, comparison, but that assumes that both zero and one are present in the number. Jul 14, 2017 at 9:12
• @MartinEnder Oh yeah RLE is a big no here. I think you suggested ri2b$e0f=:< which is longer anyways. Jul 14, 2017 at 9:13 # 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)  • Probably? Jul 13, 2017 at 15:25 • @EriktheOutgolfer At least mine has an explanation. – Jim Jul 13, 2017 at 15:32 # 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. ## 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  # Swift 3, 101 bytes func h(b:Int)->Any{let a=String(b,radix:2).characters;return a.reduce(0){$1=="1" ?$0+1:$0}>a.count/2}


Try it online

• -11 bytes: func h(b:Int){let a=String(b,radix:2).characters;print(a.filter{$1=="1"}.count>a.count/2)} Dec 12, 2017 at 16:53 • -22 bytes with Swift 4 func h(b:Int){let a=String(b,radix:2);print(a.filter{$1=="1"}.count>a.count/2)} Dec 12, 2017 at 16:58

# Perl 5, 33 bytes

$_=sprintf"%b",<>;say y/1//>y/0//  Try it online! # Add++, 12 bytes L,BBEDdb!Es<  Try it online! # C (gcc), 37 bytes i;f(n){for(;n;n/=2)i+=n%2*8-4;i=i>2;}  Idea is that we calculate difference of number of 1s and 0s multiplied by for, so we don't care that i might be 1 after previous invocation. Try it online! # SNOBOL4 (CSNOBOL4), 144 bytes  N =INPUT A O =O REMDR(N,2) N =GT(N) N / 2 :S(A) K =SIZE(O) - 1 R O 0 ='' :S(R) L =SIZE(O) OUTPUT =GE(K - L,L) 0 :F(Y)S(END) Y OUTPUT =1 END  Try it online! # Husk, 7 bytes ΣFż*gOḋ  Try it online! ### Explanation ΣFż*gOḋ -- implicit input N, for example: 5 ḋ -- convert N to base 2: [1,0,1] O -- sort: [0,1,1] g -- group equal elements: [[0],[1,1]] F -- reduce by the following (ie. apply function to the two groups*): ż* -- zip with multiplication, but keep trailing elements: [0*1,1] == [0,1] Σ -- sum: 1  * The special cases where N = 2x-1 (x = 0…) also works because a reduce (foldl1) with a singleton list simply returns that element. # cQuents, 15 bytes :uJ$);1)>uJ$);0  Note that it only works on the latest commit, had to fix a bug, so TIO may or may not work depending on when you read this. Try it online! # Explanation :uJ$);1)>uJ$);0 : Mode: sequence 1, given input n, output nth term in sequence Each term in the sequence equals: u ;1) Count number of ones in J$)                                        binary representation of current index
>            Greater than (returns 1 (truthy) if true and 0 (falsey) if false)
u   ;0)     Count number of zeroes in           (implicit closing ')')
J\$)                                  binary representation of current index