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

28
\$\begingroup\$

x86 Machine Code, 15 14 bytes

F3 0F B8 C1 0F BD D1 03 C0 42 2B D0 D6 C3

This is a function using Microsoft's __fastcall calling convention (first and only parameter in ecx, return value in eax, callee is allowed to clobber edx), though it can trivially be modified for other calling conventions that pass arguments in registers.

It returns 255 as truthy, and 0 as falsey.

It uses the undocumented (but widely supported) opcode salc.

Disassembly below:

;F3 0F B8 C1 
  popcnt eax, ecx ; Sets eax to number of bits set in ecx

;0F BD D1
  bsr edx, ecx    ; Sets edx to the index of the leading 1 bit of ecx

;03 C0
  add eax, eax

;42
  inc edx

;2B D0
  sub edx, eax

  ; At this point, 
  ;   edx = (index of highest bit set) + 1 - 2*(number of bits set)
  ; This is negative if and only if ecx was binary-heavy.

;D6
  salc           ; undocumented opcode. Sets al to 255 if carry flag 
                 ; is set, and to 0 otherwise. 

;C3
  ret

Try it online!

Thanks to Peter Cordes for suggesting replacing lzcnt with bsr.

\$\endgroup\$
  • \$\begingroup\$ Nice. I'd got as far as the obvious popcnt before scrolling down to look at answers, but hadn't thought of lzcnt for dealing with only the significant digits as required by the question. \$\endgroup\$ – Peter Cordes Jul 14 '17 at 16:42
  • \$\begingroup\$ Is there any way to get a net savings from using bsr instead of lzcnt (aka rep bsr)? You'd have to use sub instead of lea since it gives you 32-lzcnt. (Or leaves the dst unmodified for src=0, on all existing Intel and AMD hardware. AMD even documents this behaviour, but Intel says undefined... Anyway, OP said positive, which rules out 0.) \$\endgroup\$ – Peter Cordes Jul 14 '17 at 16:44
  • 1
    \$\begingroup\$ I was definitely thinking along the same lines as @Peter, since the challenge does explicitly limit inputs to positive integers. In fact, I had a solution drafted using popcnt and bsr, but it was 17 bytes. I was thinking that was pretty good compared to the first asm answer I saw, but this clever lea trick beats the pants off of that. I also looked at comparing bsf and popcnt. But I'm not seeing any way this solution can be beat, even taking into account the 1 byte that you could save by dropping the rep prefix. \$\endgroup\$ – Cody Gray Jul 14 '17 at 18:22
  • 1
    \$\begingroup\$ salc isn't equivalent to setc al: the latter sets al to 1 if CF set, not to 255. \$\endgroup\$ – Ruslan Jul 15 '17 at 8:06
  • 1
    \$\begingroup\$ The actual equivalent of salc is sbb al, al, but you get a savings of 1 byte to encode it. By the way, it is documented by AMD, and it's widely supported by Intel, with the mnemonic even coming from Intel's P6 opcode map. So this one is actually pretty safe to use. Also, nice improvement here to think to use that instruction! This is basically what my original draft did, except (1) I'd used x86-64 code, so inc was twice as long to encode, and (2) I hadn't thought of salc, so I was doing the same work in a longer way. Too bad I can only upvote once. \$\endgroup\$ – Cody Gray Jul 17 '17 at 4:57
17
\$\begingroup\$

Jelly, 5 bytes

Bo-SR

Yields non-empty output (truthy) or empty output (falsy).

Try it online!

How it works

Bo-SR  Main link. Argument: n

B      Binary; convert n to base 2.
 o-    Compute the logical OR with -1, mapping 1 -> 1 and 0 -> -1.
   S   Take the sum s. We need to check if the sum is strictly positive.
    R  Range; yield [1, ..., s], which is non-empty iff s > 0.
\$\endgroup\$
  • \$\begingroup\$ Nice. I had Bo-S, but I couldn't find a 1-byte atom that would convert positive/non-positive into truthy/falsy... \$\endgroup\$ – ETHproductions Jul 13 '17 at 15:17
  • \$\begingroup\$ Logical or with −1, right? \$\endgroup\$ – Lynn Jul 15 '17 at 9:12
  • \$\begingroup\$ @Lynn Yes, indeed. Thanks. \$\endgroup\$ – Dennis Jul 15 '17 at 15:06
  • 1
    \$\begingroup\$ 4 bytes \$\endgroup\$ – caird coinheringaahing Dec 12 '17 at 16:28
  • \$\begingroup\$ @cairdcoinheringaahing Thanks, but Æṃ didn't exist back then. \$\endgroup\$ – Dennis Dec 12 '17 at 18:01
14
\$\begingroup\$

Python 2, 35 bytes

lambda n:max('10',key=bin(n).count)

Try it online!

Old answer, 38 bytes

Outputs 0 as falsy and -2 or -1 as truthy

lambda n:~cmp(*map(bin(n).count,'10'))

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Does the leading 0 in the return of bin cause this solution problems? \$\endgroup\$ – Shadow Jul 14 '17 at 3:29
  • 3
    \$\begingroup\$ @shadow There is no problem, because of the way max works. In the event of a tie, max will return the first value in the iterable that has the maximal value. This code uses that fact to make sure that 1 is returned in the event of a tie, which actually means there are more ones than zeros, since an extra zero was added by bin. It would actually be incorrect when written this way if not for the extra zero. \$\endgroup\$ – FryAmTheEggman Jul 14 '17 at 12:47
  • \$\begingroup\$ @FryAmTheEggman this is also true on the old answer, where the cmp returns 0 when they are both equals \$\endgroup\$ – Rod Jul 14 '17 at 13:54
11
\$\begingroup\$

Octave, 18 bytes

@(n)mode(de2bi(n))

TIO doesn't work since the communications toolbox is not included. It can be tested on Octave-Online.

How this works:

de2bi converts a decimal number to a binary numeric vector, not a string as dec2bin does.

mode returns the most frequent digit in the vector. It defaults to the lowest in case of a tie.

@(n)                % Anonymous function that takes a decimal number as input 'n'
    mode(        )  % Computes the most frequent digit in the vector inside the parentheses
         de2bi(n)   % Converts the number 'n' to a binary vector
\$\endgroup\$
  • \$\begingroup\$ Is the communications toolbox a standard part of Octave, or is it more akin to a library in other languages? \$\endgroup\$ – dcsohl Jul 13 '17 at 18:28
  • \$\begingroup\$ It's a package that comes with the installation. You have to specifically load it in some installations, and it's automatically loaded as standard in others. It's part of the standard on Octave-Online.net, so I'm using that as a reference. (The code must work in at least one interpreter that existed prior to the challenge). \$\endgroup\$ – Stewie Griffin Jul 13 '17 at 18:44
9
\$\begingroup\$

JavaScript (ES6), 36 34 bytes

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0
\$\endgroup\$
  • \$\begingroup\$ f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0 for 35 bytes. \$\endgroup\$ – ovs Jul 13 '17 at 16:27
  • \$\begingroup\$ Use n>>1 instead of n>>>1 to save a byte since input is never negative. \$\endgroup\$ – kamoroso94 Jul 13 '17 at 23:00
  • \$\begingroup\$ @kamoroso94 Thanks, but then it would fail on 2147483648. \$\endgroup\$ – ETHproductions Jul 13 '17 at 23:03
  • \$\begingroup\$ @ETHproductions Darn, and n/2|0 is no better :/ \$\endgroup\$ – kamoroso94 Jul 13 '17 at 23:09
9
\$\begingroup\$

MATL, 3 bytes

BXM

Try it online!

I don't really know MATL, I just noticed that mode could work in alephalpha's Octave answer and figured there was some equivalent in MATL.

B   ' binary array from input
 XM ' value appearing most.  On ties, 0 wins
\$\endgroup\$
8
\$\begingroup\$

Mathematica, 22 bytes

Saved one byte thanks to @MartinEnder and @JungHwanMin.

#>#2&@@#~DigitCount~2&
\$\endgroup\$
  • 2
    \$\begingroup\$ I think infix notation has higher precedence than @@. \$\endgroup\$ – Martin Ender Jul 13 '17 at 20:23
  • 1
    \$\begingroup\$ -1 byte (as @MartinEnder noted): #>#2&@@#~DigitCount~2& \$\endgroup\$ – JungHwan Min Jul 14 '17 at 5:05
7
\$\begingroup\$

Brachylog, 6 bytes

ḃọtᵐ>₁

Try it online!

Explanation

Example input: 13

ḃ        Base (default: binary): [1,1,0,1]
 ọ       Occurences:             [[1,3],[0,1]]
  tᵐ     Map Tail:               [3,1]
    >₁   Strictly decreasing list

Since will never unify its output with a list of digits with leading zeroes, we know that the occurences of 1 will always be first and the occurences of 0 will always be second after .

\$\endgroup\$
7
\$\begingroup\$

Python 3,  44  (thanks @c-mcavoy) 40 bytes

lambda n:bin(n).count('0')<len(bin(n))/2

Try it online!

\$\endgroup\$
  • 5
    \$\begingroup\$ Crossed out 44 is still 44 \$\endgroup\$ – JungHwan Min Jul 14 '17 at 5:05
6
\$\begingroup\$

C (gcc), 51 48 41 40 bytes

i;f(n){for(i=0;n;n/=2)i+=n%2*2-1;n=i>0;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Based on OP's clarification, you can remove unsigned \$\endgroup\$ – musicman523 Jul 13 '17 at 15:14
  • \$\begingroup\$ Since nnn is positive, you can change n>>=1 to n/=2. I also think you can use ~n instead of n^-1, which should also allow you to change && to & \$\endgroup\$ – musicman523 Jul 13 '17 at 15:22
  • \$\begingroup\$ Weird things happen when I edit comments - "nnn" means n, and never mind about changing && to &, I don't think that would work. But changing it to * seems to work \$\endgroup\$ – musicman523 Jul 13 '17 at 15:28
  • \$\begingroup\$ @musicman523 The && was only to handle the unsigned case but since I only need to handle positive integers I can remove it all together. Good pouint about /= being shorter that >>= though, Thanks ! \$\endgroup\$ – cleblanc Jul 13 '17 at 15:32
  • \$\begingroup\$ You can save one byte changing n&1?++i:--1 to i+=n%2*2-1. You might also be able to get rid of >0 by stating that you will output zero for heavy and nonzero for not heavy \$\endgroup\$ – musicman523 Jul 13 '17 at 15:35
6
\$\begingroup\$

R, 54 53 51 bytes

-1 byte thanks to Max Lawnboy

n=scan();d=floor(log2(n))+1;sum(n%/%2^(0:d)%%2)*2>d

reads from stdin; returns TRUE for binary heavy numbers. d is the number of binary digits; sum(n%/%2^(0:d)%%2 computes the digit sum (i.e., number of ones).

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Only saw your answer after posting mine... Anyway, you can use log2(n) instead of log(n,2) to save 1 byte \$\endgroup\$ – Maxim Mikhaylov Jul 13 '17 at 20:14
  • \$\begingroup\$ @MaxLawnboy ah, of course. Thanks! \$\endgroup\$ – Giuseppe Jul 13 '17 at 20:38
  • \$\begingroup\$ Golfed off another 12 bytes: codegolf.stackexchange.com/a/132396/59530 \$\endgroup\$ – JAD Jul 14 '17 at 10:23
6
\$\begingroup\$

x86_64 machine code, 23 22 21 bytes

31 c0 89 fa 83 e2 01 8d 44 50 ff d1 ef 75 f3 f7 d8 c1 e8 1f c3

Disassembled:

  # zero out eax
  xor  %eax, %eax
Loop:
  # copy input to edx
  mov  %edi, %edx
  # extract LSB(edx)
  and  $0x1, %edx
  # increment(1)/decrement(0) eax depending on that bit
  lea -1(%rax,%rdx,2), %eax
  # input >>= 1
  shr  %edi
  # if input != 0: repeat from Loop
  jnz  Loop

  # now `eax < 0` iff the input was not binary heavy,
  neg %eax
  # now `eax < 0` iff the input was binary heavy (which means the MSB is `1`)
  # set return value to MSB(eax)
  shr  $31, %eax
  ret

Thanks @Ruslan, @PeterCordes for -1 byte!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Is there any particular reason why you use 8d 1f instead of 89 fb? \$\endgroup\$ – Ruslan Jul 13 '17 at 17:30
  • 2
    \$\begingroup\$ The real question is, is there any particular reason why you're using that abominable AT&T syntax?!? Also, the disassembly and your disassembly both agree that you have add eax, 2+dec eax, but your comments suggest that you want to increment ebx, not eax. \$\endgroup\$ – Cody Gray Jul 14 '17 at 4:23
  • 1
    \$\begingroup\$ You can replace jnz Next/add/dec (7 bytes) with lea -1(%rax, %rbx, 2), %eax (4 bytes) to do eax += 2*ebx - 1 (like in the other x86 machine-code answer). Then outside the loop, neg %eax (2 bytes) before shifting the sign bit to the bottom. Net saving of 1 byte. Or test %eax,%eax / setge %al would also work, if your return value is a bool or int8_t. \$\endgroup\$ – Peter Cordes Jul 14 '17 at 17:17
  • 1
    \$\begingroup\$ @PeterCordes I think I know what happened, but I'm not sure: I might have not tried lea -1(%rax,rbx,2) but only lea -1(%eax,%eax,2) and wasted bytes this way.. Anyway, you both were right, I can save a byte like this. Thanks a lot (in return I'll change that lea to a mov while I'm at it)! \$\endgroup\$ – ბიმო Jul 14 '17 at 18:01
  • 1
    \$\begingroup\$ @moonheart08: I didn't know about that back then, but someone posted an answer which saved 7 bytes. \$\endgroup\$ – ბიმო Feb 7 at 16:10
5
\$\begingroup\$

Perl 6,  32  30 bytes

{[>] .base(2).comb.Bag{qw<1 0>}}

Test it

{[>] .polymod(2 xx*).Bag{1,0}}

Test it

Expanded:

{      # bare block lambda with implicit parameter 「$_」

  [>]  # reduce the following with &infix:« > »

    .polymod(2 xx *) # turn into base 2 (reversed) (implicit method call on 「$_」)
    .Bag\            # put into a weighted Set
    { 1, 0 }         # key into that with 1 and 0
                     # (returns 2 element list that [>] will reduce)
}
\$\endgroup\$
5
\$\begingroup\$

Wise, 40 39 bytes

::^?[:::^~-&[-~!-~-~?]!~-?|>]|:[>-?>?]|

Try it online!

Explanation

::^?                                      Put a zero on the bottom
    [                                     While
     :::^~-&                              Get the last bit
            [-~!-~-~?]!~-?|               Increment counter if 0 decrement if 1
                           >              Remove the last bit
                            ]|            End while
                              :[>-?>?]|   Get the sign
\$\endgroup\$
5
\$\begingroup\$

Haskell, 41 34

g 0=0
g n=g(div n 2)+(-1)^n
(<0).g

If n is odd, take a -1 if it's even, take a 1. Add a recursive call with n/2 and stop if n = 0. If the result is less than 0 the number is binary-heavy.

Try it online!

Edit: @Ørjan Johansen found some shortcuts and saved 7 bytes. Thanks!

\$\endgroup\$
  • \$\begingroup\$ mod n 2 can be just n, and it's a byte shorter without an accumulator. Try it online! \$\endgroup\$ – Ørjan Johansen Jul 13 '17 at 15:38
5
\$\begingroup\$

Retina, 37 34 bytes

.+
$*
+`(1+)\1
$1@
@1
1
+`.\b.

1+

Try it online! Link includes smaller test cases (the larger ones would probably run out of memory). Edit: Saved 3 bytes thanks to @MartinEnder. Explanation: The first stage converts from decimal to unary, and the next two stages convert from unary to binary (this is almost straight out of the unary arithmetic page on the Retina wiki, except that I'm using @ instead of 0). The third stage looks for pairs of dissimilar characters, which could be either @1 or 1@, and deletes them until none remain. The last stage then checks for remaining 1s.

\$\endgroup\$
  • \$\begingroup\$ ${1} can be $+. Or you could use ! instead of 0 and then shorten 01|10 to .\b.. \$\endgroup\$ – Martin Ender Jul 13 '17 at 20:25
  • \$\begingroup\$ @MartinEnder Huh, does $+ do the right thing when the pattern contains a |? I wonder whether I could have used that before... \$\endgroup\$ – Neil Jul 13 '17 at 20:42
  • 2
    \$\begingroup\$ no, $+ is super stupid and simply uses the group with the biggest number, whether it was used or not. It's only useful for golfing when you've got more than nine groups or in a situation like the one here, and I don't know why I'd ever use it in a production regex. \$\endgroup\$ – Martin Ender Jul 13 '17 at 20:43
5
\$\begingroup\$

R, 43 bytes

max(which(B<-intToBits(scan())>0))/2<sum(B)

Try it online!

             intToBits(scan())              # converts to bits
          B<-                 >0            # make logical and assign to B
max(which(                      ))/2        # get the length of the trimmed binary and halve
                                    <sum(B) # test against the sum of bits
\$\endgroup\$
5
\$\begingroup\$

Kotlin, 50 bytes

{i:Int->i.toString(2).run{count{it>'0'}>length/2}}

Lambda of implicit type (Int) -> Boolean. Version 1.1 and higher only due to usage of Int.toString(radix: Int).

Unfortunately TIO's Kotlin runtime seems to be 1.0.x, so here's a sad dog instead of a TIO link:

\$\endgroup\$
4
\$\begingroup\$

Pyth, 9 7 bytes

ehc2S.B

Try it here.

-2 thanks to FryAmTheEggman.

\$\endgroup\$
  • \$\begingroup\$ Another 9 byte approach: >ysJjQ2lJ \$\endgroup\$ – KarlKastor Jul 13 '17 at 17:11
  • 1
    \$\begingroup\$ 7 bytes but I feel like there should still be something shorter... \$\endgroup\$ – FryAmTheEggman Jul 13 '17 at 21:06
  • \$\begingroup\$ @FryAmTheEggman Hmm...that could only work as a full program. (I knew there was a way to use .B!) \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 9:08
4
\$\begingroup\$

R, 39 37 bytes

sum(intToBits(x<-scan())>0)>2+log2(x)

This is a combination of the methods used by @MickyT and @Giuseppe, saving another few bytes.

sum(intToBits(x) > 0) counts the amount of 1 bits, and 2+log2(x)/2 is half of the total amount of bits, when rounded down. We don't have to round down because of the behaviour when the two values are equal.

\$\endgroup\$
4
\$\begingroup\$

C# (.NET Core), 62, 49 bytes

Without LINQ.

EDIT: dana with a -13 byte golf changing the while to a recursive for and returning a bool instead of integer.

x=>{int j=0;for(;x>0;x/=2)j+=x%2*2-1;return j>0;}

Try it online!

\$\endgroup\$
4
+100
\$\begingroup\$

Regex (ECMAScript), 85 73 71 bytes

^((?=(x*?)\2(\2{4})+$|(x*?)(\4\4xx)*$)(\2\4|(x*)\5\7\7(?=\4\7$\2)\B))*$

Try it online!

explanation by Deadcode

The earlier 73 byte version is explained below.

^((?=(x*?)\2(\2{4})+$)\2|(?=(x*?)(\4\4xx)*$)(\4|\5(x*)\7\7(?=\4\7$)\B))+$

Because of the limitations of ECMAScript regex, an effective tactic is often to transform the number one step at a time while keeping the required property invariant at every step. For example, to test for a perfect square or a power of 2, reduce the number in size while keeping it a square or power of 2 (respectively) at every step.

Here is what this solution does at every step:

If the rightmost bit is not a 1, the rightmost 1 bit (if it is not the only 1 bit, i.e. if the current number is not a power of 2) is moved one step to the right, effectively changing a 10 to a 01 (for example, 11011000 → 11010100 → 11010010 → 11010001), which has no effect on the number's binary-heaviness. Otherwise, the rightmost 01 is deleted (for example 10111001 → 101110, or 1100111 → 11011). This also has no effect on the number's heaviness, because the truth or falsehood of \$ones>zeroes\$ will not change if \$1\$ is subtracted from both; that is to say,

\$ones>zeroes⇔ones-1>zeroes-1\$

When these repeated steps can go no further, the end result will either be a contiguous string of 1 bits, which is heavy, and indicates that the original number was also heavy, or a power of 2, indicating that the original number was not heavy.

And of course, although these steps are described above in terms of typographic manipulations on the binary representation of the number, they're actually implemented as unary arithmetic.

# For these comments, N = the number to the right of the "cursor", a.k.a. "tail",
# and "rightmost" refers to the big-endian binary representation of N.
^
(                          # if N is even and not a power of 2:
    (?=(x*?)\2(\2{4})+$)   # \2 = smallest divisor of N/2 such that the quotient is
                           # odd and greater than 1; as such, it is guaranteed to be
                           # the largest power of 2 that divides N/2, iff N is not
                           # itself a power of 2 (using "+" instead of "*" is what
                           # prevents a match if N is a power of 2).
    \2                     # N = N - \2. This changes the rightmost "10" to a "01".
|                          # else (N is odd or a power of 2)
    (?=(x*?)(\4\4xx)*$)    # \4+1 = smallest divisor of N+1 such that the quotient is
                           # odd; as such, \4+1 is guaranteed to be the largest power
                           # of 2 that divides N+1. So, iff N is even, \4 will be 0.
                           # Another way of saying this: \4 = the string of
                           # contiguous 1 bits from the rightmost part of N.
                           # \5 = (\4+1) * 2 iff N+1 is not a power of 2, else
                           # \5 = unset (NPCG) (iff N+1 is a power of 2), but since
                           #   N==\4 iff this is the case, the loop will exit
                           #   immediately anyway, so an unset \5 will never be used.
    (
        \4                 # N = N - \4. If N==\4 before this, it was all 1 bits and
                           # therefore heavy, so the loop will exit and match. This
                           # would work as "\4$", and leaving out the "$" is a golf
                           # optimization. It still works without the "$" because if
                           # N is no longer heavy after having \4 subtracted from it,
                           # this will eventually result in a non-match which will
                           # then backtrack to a point where N was still heavy, at
                           # which point the following alternative will be tried.
    |
        # N = (N + \4 - 2) / 4. This removes the rightmost "01". As such, it removes
        # an equal number of 0 bits and 1 bits (one of each) and the heaviness of N
        # is invariant before and after. This fails to match if N is a power of 2,
        # and in fact causes the loop to reach a dead end in that case.
        \5                 # N = N - (\4+1)*2
        (x*)\7\7(?=\4\7$)  # N = (N - \4) / 4 + \4
        \B                 # Assert N > 0 (this would be the same as asserting N > 2
                           # before the above N = (N + \4 - 2) / 4 operation).
    )
)+
$       # This can only be a match if the loop was exited due to N==\4.
\$\endgroup\$
  • 2
    \$\begingroup\$ While this is inspired by Deadcode's answer, the algorithm is different enough that I felt it deserved a separate answer rather than a comment. \$\endgroup\$ – Grimy Feb 6 at 16:17
  • 2
    \$\begingroup\$ This is phenomenal, and exactly what I wanted to see (somebody blowing my regex out of the water with a much more concise algorithm). But your comments really don't explain it at all, and the commented 73-byte version of the regex does not even work (the backrefs \5 onward are off by one). I have studied this and explained and commented it in my answer (because StackExchange doesn't allow multiline replies). \$\endgroup\$ – Deadcode Feb 7 at 3:31
4
\$\begingroup\$

Regex (ECMAScript), 183 bytes

This was another interesting problem to solve with ECMA regex. The "obvious" way to handle this is to count the number of 1 bits and compare that to the total number of bits. But you can't directly count things in ECMAScript regex – the lack of persistent backreferences means that only one number may be modified in a loop, and at each step it can only be decreased.

This unary algorithm works as follows:

  1. Take the square root of the largest power of 2 that fits into N, and take note of whether the square root was perfect or had to be rounded down. This will be used later.
  2. In a loop, move each most-significant 1 bit to the least-significant position where there is a 0 bit. Each of these steps is a subtraction. At the end of the loop, the remaining number (as it would be represented in binary) is a string of 1s with no 0s. These operations are actually done in unary; it's only conceptually that they are being done in binary.
  3. Compare this "binary string of 1s" against the square root obtained earlier. If the square root had to be rounded down, use a doubled version of it. This ensures that the "binary string of 1s" is required to have more than half as many binary digits as N in order for there to be a final match.

To obtain the square root, a variant of the multiplication algorithm briefly described in my Rocco numbers regex post is used. To identify the least-significant 0 bit, the division algorithm briefly described in my factorial numbers regex post is used. These are spoilers. So do not read any further if you don't want some advanced unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in the list of consecutively spoiler-tagged recommended problems in this earlier post, and trying to come up with the mathematical insights independently.

With no further ado, the regex:

^(?=.*?(?!(x(xx)+)\1*$)(x)*?(x(x*))(?=(\4*)\5+$)\4*$\6)(?=(((?=(x(x+)(?=\10$))*(x*))(?!.*$\11)(?=(x*)(?=(x\12)*$)(?=\11+$)\11\12+$)(?=.*?(?!(x(xx)+)\14*$)\13(x*))\16)*))\7\4(.*$\3|\4)

Try it online!

# For the purposes of these comments, the input number = N.
^
# Take the floor square root of N
(?=
    .*?
    (?!(x(xx)+)\1*$)    # tail = the largest power of 2 less than tail
    (x)*?               # \3 = nonzero if we will need to round this square root
                        #      up to the next power of two
    (x(x*))             # \4 = potential square root; \5 = \4 - 1
    (?=
        (\4*)\5+$       # Iff \4*\4 == our number, then the first match here must result in \6==0
    )
    \4*$\6              # Test for divisibility by \4 and for \6==0 simultaneously
)
# Move all binary bits to be as least-significant as possible, e.g. 11001001 -> 1111
(?=
    (                                 # \7 = tool for making tail = the result of this move
        (
            (?=
                (x(x+)(?=\10$))*(x*)  # \11 = {divisor for getting the least-significant 0 bit}-1
            )
            (?!.*$\11)                # Exit the loop when \11==0
            (?=
                (x*)                  # \12 = floor((tail+1) / (\11+1)) - 1
                (?=(x\12)*$)          # \13 = \12+1
                (?=\11+$)
                \11\12+$
            )
            (?=
                .*?
                (?!(x(xx)+)\14*$)     # tail = the largest power of 2 less than tail
                \13                   # tail -= \13
                (x*)                  # \16 = tool to move the most-significant 1 bit to the
                                      # least-significant 0 bit available spot for it
            )
            \16
        )*
    )
)
\7                  # tail = the result of the move
\4                  # Assert that \4 is less than or equal to the result of the move
(
    .*$\3
|
    \4              # Double the value of \4 to compare against if \3 is non-empty,
                    # i.e. if we had an even number of total digits.
)
\$\endgroup\$
3
\$\begingroup\$

Jelly, 6 bytes

Bµċ0<S

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Bo-S can be used to calculate the binary "weight" of the input, unfortunately the shortest way to use that appears to be Bo-S>0... \$\endgroup\$ – ETHproductions Jul 13 '17 at 15:11
  • \$\begingroup\$ @ETHproductions Yep, there's no "is positive" atom yet. \$\endgroup\$ – Erik the Outgolfer Jul 13 '17 at 15:17
  • \$\begingroup\$ Well apparently works :P \$\endgroup\$ – ETHproductions Jul 13 '17 at 15:18
3
\$\begingroup\$

J, 12 bytes

(+/>-:@#)@#:

J executes verbs right-to-left, so let's start at the end and work our way towards the beginning.

Explanation

         #:       NB. Convert input to list of bits
       -:@#       NB. Half (-:) the (@) length (#)
          >       NB. Greater than 
         +/       NB. Sum (really plus (+) reduce (/)
\$\endgroup\$
  • 1
    \$\begingroup\$ (#<2*+/)@#: should save 1 unless I’m missing something. \$\endgroup\$ – FrownyFrog Dec 12 '17 at 17:58
3
\$\begingroup\$

Julia, 22 bytes

x->2*x<4^count_ones(x)
\$\endgroup\$
2
\$\begingroup\$

Octave, 26 bytes

@(a)sum(2*dec2bin(a)-97)>0

Try it online!

\$\endgroup\$
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\$
  • \$\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\$ – GalacticCowboy Jul 13 '17 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\$ – TheLethalCoder Jul 14 '17 at 7:52

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.