74
\$\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\$ Commented Jul 13, 2017 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\$
    – Mayube
    Commented Jul 13, 2017 at 14:53
  • \$\begingroup\$ Does any truthy/falsy value count or do we need two distinct values? \$\endgroup\$ Commented Jul 13, 2017 at 15:22
  • \$\begingroup\$ @EriktheOutgolfer any value \$\endgroup\$
    – Mayube
    Commented Jul 13, 2017 at 15:35
  • 11
    \$\begingroup\$ Aka A072600, if this helps anybody. \$\endgroup\$
    – dcsohl
    Commented Jul 13, 2017 at 17:59

97 Answers 97

2
\$\begingroup\$

PHP, 44 bytes

for(;$a=&$argn;$a>>=1)$r+=$a&1?:-1;echo$r>0;

Try it online!

PHP, 48 bytes

<?=($c=count_chars(decbin($argn)))[49]-$c[48]>0;

Try it online!

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

Python 2, 44 bytes

f=lambda n,c=0:f(n/2,c+n%2*2-1)if n else c>0

Try it online!

Old Answer, 47 bytes

c,n=0,input()
while n:c+=n%2*2-1;n/=2
print c>0

This is simply a port of @cleblanc's C answer. It's longer than other Python answers but I figured it was worth posting since it's a completely different method of finding the answer.

Try it online!

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

C#, 82 bytes

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}
\$\endgroup\$
2
  • \$\begingroup\$ You can trim some more by treating the string as an IEnumerable<char>. n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;} \$\endgroup\$ Commented Jul 13, 2017 at 19:43
  • \$\begingroup\$ @GalacticCowboy That adds 11 bytes because you have to fully qualify Convert and include using System.Linq; (written shorter as namespace System.Linq{}). Nice idea just doesn't shave off enough to warrant the saving in this case. \$\endgroup\$ Commented Jul 14, 2017 at 7:52
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
    Commented Jul 13, 2017 at 20:45
  • \$\begingroup\$ @Giuseppe Very neat shortcut with sum(n|T). Thanks! \$\endgroup\$ Commented Jul 13, 2017 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
    Commented May 2, 2018 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\$ Commented Jul 14, 2017 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
    Commented Jul 14, 2017 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
    Commented Jul 14, 2017 at 13:29
  • \$\begingroup\$ If you use Java 9's JShell you don't need the import since java.math.* is imported implicitly. \$\endgroup\$ Commented Aug 3, 2017 at 15:13
  • \$\begingroup\$ @DavidConrad Thanks, it seems to have a usefult list of default imports for golfing \$\endgroup\$
    – JollyJoker
    Commented Aug 4, 2017 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\$
1
  • \$\begingroup\$ 11 bytes in q: .5<avg 2 vs \$\endgroup\$ Commented Nov 21, 2022 at 4:24
2
\$\begingroup\$

Python, 33 bytes

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

Try it online!

\$\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\$

Ruby, 30 27 bytes

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

Try it online!

\$\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
    Commented Dec 20, 2020 at 12:10
2
\$\begingroup\$

Factor, 35 13 bytes

[ >bin mode ]

Try it online!

Outputs 49 for truthy and 48 for falsey.

  • >bin Convert input integer to binary string
  • mode Return the character that occurs most often (ties return 48)
\$\endgroup\$
2
\$\begingroup\$

Arturo, 36 bytes

$=>[<size d--1∑d:<=digits.base:2&]

Try it

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

Uiua, 12 11 8 bytes

<×2⊃/+⧻⋯

Try it!

<×2⊃/+⧻⋯
       ⋯  # convert number to bit array
      ⧻   # length
    /+    # sum
   ⊃      # fork (do sum and length on the same value)
 ×2       # double
<         # less than
\$\endgroup\$
2
\$\begingroup\$

Ruby, 39 32 bytes

->n{b=n.digits 2;b.sum>b.size/2}

Attempt This Online!

\$\endgroup\$
1
  • 2
    \$\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
    Commented Jul 17, 2017 at 12:36
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\$ Commented Jul 17, 2017 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\$

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
    Commented Jul 15, 2017 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\$

Pyt, 4 bytes

←ɓąṀ

Explanation:

←             Get input
 ɓ            Get binary representation as string
  ą           Convert to array of digits
   Ṁ          Get the mode of the array (this returns the smallest if there are multiple)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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