29
\$\begingroup\$

Input

The input is a single positive integer n

Output

The output isn with its most significant bit set to 0.

Test Cases

1 -> 0
2 -> 0
10 -> 2
16 -> 0
100 -> 36
267 -> 11
350 -> 94
500 -> 244

For example: 350 in binary is 101011110. Setting its most significant bit (i.e. the leftmost 1 bit) to 0 turns it into 001011110 which is equivalent to the decimal integer 94, the output. This is OEIS A053645.

\$\endgroup\$
  • 18
    \$\begingroup\$ Clearing the most significant bit from 10 obviously gives 0 :D \$\endgroup\$ – clabacchio Nov 15 '17 at 10:26
  • \$\begingroup\$ @clabacchio I.. it... er... wha? (nice one) \$\endgroup\$ – Baldrickk Nov 15 '17 at 10:46
  • 12
    \$\begingroup\$ It seems to me that the zeroes are just as significant as the ones. When you say "the most significant bit" you mean "the most significant bit that is set to one". \$\endgroup\$ – Michael Kay Nov 16 '17 at 18:54

75 Answers 75

12
\$\begingroup\$

C (gcc), 49 44 40 39 bytes

i;f(n){for(i=1;n/i;i*=2);return n^i/2;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace i<=n with n/i for -1 byte. This isn't my golf, someone else tried to edit it into your post but I rolled it back because edits for golfing posts are not accepted according to our community rules. \$\endgroup\$ – HyperNeutrino Nov 15 '17 at 13:54
  • 1
    \$\begingroup\$ @HyperNeutrino I saw and approved the edit just now. Wasn't aware of that rule but it's a nice golfing tip! \$\endgroup\$ – cleblanc Nov 15 '17 at 13:55
  • \$\begingroup\$ Ah okay. Yeah typically people are supposed to post comments for golfing tips and OP should make the edits, but if you accepted it, it's not really as much of a problem. :) \$\endgroup\$ – HyperNeutrino Nov 15 '17 at 13:56
10
\$\begingroup\$

Python 2, 27 bytes

lambda n:n^2**len(bin(n))/8

Try it online!

26 bytes

Unfortunately, this does not work for 1:

lambda n:int(bin(n)[3:],2)

Try it online!

\$\endgroup\$
9
\$\begingroup\$

05AB1E, 5 bytes

.²óo-

Try it online!

Removing the most significant bit from an integer N is equivalent to finding the distance from N to the highest integer power of 2 lower than N.

Thus, I used the formula N - 2floor(log2N):

  • - Logarithm with base 2.
  • ó - Floor to an integer.
  • o - 2 raised to the power of the result above.
  • - - Difference.
\$\endgroup\$
  • 1
    \$\begingroup\$ b¦C also works... doesn't it? Convert to binary, MSB is always at index 1, remove MSB, convert back. \$\endgroup\$ – Magic Octopus Urn Nov 15 '17 at 12:01
  • 2
    \$\begingroup\$ @MagicOctopusUrn No that is wrong, fails for 1! \$\endgroup\$ – Mr. Xcoder Nov 15 '17 at 12:15
8
\$\begingroup\$

Jelly, 3 bytes

BḊḄ

Try it online!

Explanation

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary
\$\endgroup\$
  • 2
    \$\begingroup\$ Aren't and two-byte codepoints? This would change the overall size to 5 bytes. \$\endgroup\$ – Bartek Banachewicz Nov 15 '17 at 12:30
  • 3
    \$\begingroup\$ @BartekBanachewicz Jelly uses its own codepage, where those chars are only 1 byte. \$\endgroup\$ – steenbergh Nov 15 '17 at 12:53
  • 1
    \$\begingroup\$ Thanks for asking and answering this, that has bugged me for a long time! \$\endgroup\$ – Ukko Nov 15 '17 at 15:08
8
\$\begingroup\$

C (gcc) -- 59 bytes

main(i){scanf("%d",&i);return i&~(1<<31-__builtin_clz(i));}

This gcc answer uses only integer bitwise and arithmetic operations. No logarithms here! It may have issues with an input of 0, and is totally non-portable.

It's my first answer on this site, so I'd love feedback and improvements. I sure had fun with learning bitwise expressions.

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

MATL, 8 6 bytes

B0T(XB

Try it online!

Saved two bytes thanks to Cinaski. Switching to assignment indexing instead of reference indexing was 2 bytes shorter :)

Explanation:

          % Grab input implicitly: 267
B         % Convert to binary: [1 0 0 0 0 1 0 1 1]
 0T(      % Set the first value to 0: [0 0 0 0 0 1 0 1 1]
    XB    % Convert to decimal: 11
\$\endgroup\$
  • 1
    \$\begingroup\$ You could have used reference indexing (also for 6 bytes), if you used 4L rather than [2J]. Another fun 6 bytes: tZlcW- (only works in MATLAB, not in TIO/Octave) \$\endgroup\$ – Sanchises Nov 15 '17 at 9:19
6
\$\begingroup\$

Java (OpenJDK 8), 23 bytes

n->n^n.highestOneBit(n)

Try it online!

Sorry, built-in :-/

\$\endgroup\$
  • \$\begingroup\$ Java with a build-in that some other popular languages like .NET and Python has not?! o.Ô +1 to that. Was about to post something longer without build-ins.. Yours is 15 bytes shorter. XD \$\endgroup\$ – Kevin Cruijssen Nov 15 '17 at 11:14
  • \$\begingroup\$ @KevinCruijssen Something like n->n^1<<(int)Math.log2(n) will work and is likely shorter than 38 bytes. It was my second (yet untested) idea, if the highestOneBit one didn't work appropriately. Out of curiosity, what was your solution \$\endgroup\$ – Olivier Grégoire Nov 15 '17 at 20:54
  • \$\begingroup\$ Mine was n->n^1<<(int)(Math.log(n)/Math.log(2)) because Math.log2 doesn't exist in Java. ;P Only Math.log, Math.log10 and Math.loglp are available. \$\endgroup\$ – Kevin Cruijssen Nov 16 '17 at 7:57
  • 2
    \$\begingroup\$ I was going to post the same, only minus instead of xor. Remembered the method from this \$\endgroup\$ – JollyJoker Nov 16 '17 at 8:26
  • 1
    \$\begingroup\$ @KevinCruijssen Oops, Math.log2 doesn't exist indeed... My bad. See? One nice method (highestOneBit) exists but not another one (Math.log2). Java is weird ;-) \$\endgroup\$ – Olivier Grégoire Nov 16 '17 at 8:41
6
\$\begingroup\$

Husk, 3 bytes

ḋtḋ

Try it online!

Explanation:

    -- implicit input, e.g. 350
  ḋ -- convert number to list of binary digits (TNum -> [TNum]): [1,0,1,0,1,1,1,1,0]
 t  -- remove first element: [0,1,0,1,1,1,1,0]
ḋ   -- convert list of binary digits to number ([TNum] -> TNum): 94
\$\endgroup\$
  • \$\begingroup\$ Similarly to the Jelly solution, this seems like it's actually 5 bytes, not 3. \$\endgroup\$ – Bartek Banachewicz Nov 15 '17 at 12:31
  • 1
    \$\begingroup\$ @BartekBanachewicz Similarly to Jelly, Husk uses its own codepage, so this is actually 3 bytes :P \$\endgroup\$ – HyperNeutrino Nov 15 '17 at 13:00
  • \$\begingroup\$ @BartekBanachewicz See here for the codepage: github.com/barbuz/Husk/wiki/Codepage \$\endgroup\$ – Laikoni Nov 15 '17 at 13:08
5
\$\begingroup\$

Ohm v2, 3 bytes

b(ó

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Python 2, 27 bytes

lambda n:n-2**len(bin(n))/8

Try it online!

Explanation

lambda n:n-2**len(bin(n))/8  # Lambda Function: takes `n` as an argument
lambda n:                    # Declaration of Lambda Function
              len(bin(n))    # Number of bits + 2
           2**               # 2 ** this ^
                         /8  # Divide by 8 because of the extra characters in the binary representation
         n-                  # Subtract this from the original
\$\endgroup\$
  • \$\begingroup\$ ...Just when I was working the bitwise math out. :P \$\endgroup\$ – totallyhuman Nov 14 '17 at 19:05
  • \$\begingroup\$ @totallyhuman heh sorry but beat you to it :P \$\endgroup\$ – HyperNeutrino Nov 14 '17 at 19:05
  • \$\begingroup\$ 2**len(bin(n))/8 can also be spelled 1<<len(bin(n))-3, and then it will work in both 2 and 3 (no bytes saved/added). \$\endgroup\$ – Mego Nov 14 '17 at 19:08
  • \$\begingroup\$ @Mego Cool, thanks for the addition! \$\endgroup\$ – HyperNeutrino Nov 14 '17 at 19:08
5
\$\begingroup\$

Python 3, 30 bytes

-8 bytes thanks to caird coinheringaahing. I typed that from memory. :o

lambda n:int('0'+bin(n)[3:],2)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Why not lambda n:int(bin(n)[3:],2)? \$\endgroup\$ – caird coinheringaahing Nov 14 '17 at 21:02
  • \$\begingroup\$ Well, a) that would error on 1, b) I'm dumb enough to not think of that. But I did fix it with a minor change. Thanks! \$\endgroup\$ – totallyhuman Nov 14 '17 at 21:06
  • \$\begingroup\$ I've edited the code so that it works, (and saves 4 bytes) \$\endgroup\$ – caird coinheringaahing Nov 14 '17 at 21:07
  • \$\begingroup\$ That still errors on 1. \$\endgroup\$ – totallyhuman Nov 14 '17 at 21:08
  • \$\begingroup\$ @cairdcoinheringaahing That was my original answer, but then I realised it errored on 1. The workaround ends up longer than a simple XOR method \$\endgroup\$ – FlipTack Nov 14 '17 at 21:52
4
\$\begingroup\$

Mathematica, 37 bytes

Rest[#~IntegerDigits~2]~FromDigits~2&

Try it online!

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

JavaScript, 22 20 bytes

Saved 2 bytes thanks to ovs

a=>a^1<<Math.log2(a)

Try it online!

Another approach, 32 bytes

a=>'0b'+a.toString`2`.slice`1`^0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ why would you do .slice`1`^0 when .slice(1)^0 would work just as well, haha \$\endgroup\$ – ETHproductions Nov 15 '17 at 0:19
  • \$\begingroup\$ @ETHproductions. This one looks better :) \$\endgroup\$ – user72349 Nov 15 '17 at 7:54
4
\$\begingroup\$

J, 6 bytes

}.&.#:

Pretty simple.

Explanation

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead
\$\endgroup\$
  • \$\begingroup\$ I was going to post this :( \$\endgroup\$ – Cyoce Nov 15 '17 at 6:07
  • \$\begingroup\$ @Cyoce Me too... \$\endgroup\$ – Adám Nov 15 '17 at 9:52
4
\$\begingroup\$

APL (Dyalog), 10 bytes

Tacit prefix function.

2⊥1↓2∘⊥⍣¯1

Try it online!

2∘⊥… decode from base-2…
 …⍣¯1 negative one time (i.e. encode in base-2)

1↓ drop the first bit

2⊥ decode from base-2

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

Ruby, 26 bytes

-7 Bytes thanks to Ventero. -2 Bytes thanks to historicrat.

->n{/./=~'%b'%n;$'.to_i 2}
\$\endgroup\$
  • \$\begingroup\$ You can save a few bytes by just skipping the first character and dropping redundant parentheses: ->n{n.to_s(2)[1..-1].to_i 2} \$\endgroup\$ – Ventero Nov 14 '17 at 21:37
  • \$\begingroup\$ ->n{/./=~'%b'%n;$'.to_i 2} \$\endgroup\$ – histocrat Nov 14 '17 at 23:11
4
\$\begingroup\$

C (gcc), 38 bytes

Built-in in gcc used.

f(c){return c^1<<31-__builtin_clz(c);}
\$\endgroup\$
  • \$\begingroup\$ Replacing 31- with ~ should save two bytes. \$\endgroup\$ – user72349 Nov 15 '17 at 18:36
  • \$\begingroup\$ @ThePirateBay it depends on hardware whether the shift is masked. On my computer, it will output 0. \$\endgroup\$ – Colera Su Nov 16 '17 at 14:35
4
\$\begingroup\$

ARM Assembly, 46 43 bytes

(You can omit destination register on add when same as source)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret
\$\endgroup\$
  • \$\begingroup\$ What flavour of ARM assembly syntax is this? My GNU assembler doesn't understand shr/shl/ret and wants instead something like lsr/lsl/bx lr. \$\endgroup\$ – Ruslan Nov 16 '17 at 20:19
  • \$\begingroup\$ Probably mixing syntax across multiple versions (ret is from aarch64), though I thought that the assembler would pseudo op these for you. For purposes of here, though, using the older and direct lsl/lsr is probably correct. \$\endgroup\$ – Michael Dorgan Nov 17 '17 at 17:44
  • \$\begingroup\$ Funny thing, i can do it in 1 less operation, but I the byte size goes up by 2. Ah code golf. \$\endgroup\$ – Michael Dorgan Nov 20 '17 at 18:43
3
\$\begingroup\$

Pyth, 5 bytes

a^2sl

Test suite.

Explanation:

    l   Log base 2 of input.
   s    Cast ^ to integer (this is the position of the most significant bit.)
 ^2     Raise 2 to ^ (get the value of said bit)
a       Subtract ^ from input
\$\endgroup\$
3
\$\begingroup\$

Alice, 8 bytes

./-l
o@i

Try it online!

Explanation

.   Duplicate an implicit zero at the bottom of the stack. Does nothing.
/   Switch to Ordinal mode, move SE.
i   Read all input as a string.
l   Convert to lower case (does nothing, because the input doesn't contain letters).
i   Try reading all input again, pushes an empty string.
/   Switch to Cardinal mode, move W.
.   Duplicate. Since we're in Cardinal mode, this tries to duplicate an integer.
    To get an integer, the empty string is discarded implicitly and the input is 
    converted to the integer value it represents. Therefore, at the end of this,
    we get two copies of the integer value that was input.
l   Clear lower bits. This sets all bits except the MSB to zero.
-   Subtract. By subtracting the MSB from the input, we set it to zero. We could
    also use XOR here.
/   Switch to Ordinal, move NW (and immediately reflect to SW).
o   Implicitly convert the result to a string and print it.
/   Switch to Ordinal, move S.
@   Terminate the program.
\$\endgroup\$
3
\$\begingroup\$

Japt, 6 bytes

^2p¢ÊÉ

Try it online!

Explanation

^2p¢ÊÉ
   ¢     Get binary form of input
    Ê    Get length of that
     É   Subtract 1
 2p      Raise 2 to the power of that
^        XOR with the input

If input 1 can fail: 4 bytes

¢Ån2

Try it online!

Explanation: get input binary (¢), slice off first char (Å), parse as binary back to a number (n2).

\$\endgroup\$
3
\$\begingroup\$

Octave, 20 bytes

@(x)x-2^fix(log2(x))

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 9 bytes

⊢-2*∘⌊2⍟⊢

Try it online!

-1 byte thanks to Adam

\$\endgroup\$
  • \$\begingroup\$ Completely correct, although I would have used TIO to generate a template for me. Anyway, ⊢-2*∘⌊2⍟⊢ saves a byte. \$\endgroup\$ – Adám Nov 14 '17 at 19:37
  • \$\begingroup\$ I was sad that APL wasn't represented, and there is was, almost lost in the scroll! I miss APL. \$\endgroup\$ – cmm Nov 15 '17 at 0:47
  • \$\begingroup\$ @cmm APL is alive and well. Feel free to hang out in the Stack Exchange APL chat room. \$\endgroup\$ – Adám Nov 15 '17 at 9:46
3
\$\begingroup\$

CJam, 7 bytes

{2b()b}

Try it online!

Explanation:

{     }  Block:         267
 2b      Binary:        [1 0 0 0 0 1 0 1 1]
   (     Pop:           [0 0 0 0 1 0 1 1] 1
    )    Increment:     [0 0 0 0 1 0 1 1] 2
     b   Base convert:  11

Reuse the MSB (which is always 1) to avoid having to delete it; the equivalent without that trick would be {2b1>2b} or {2b(;2b}.

\$\endgroup\$
3
\$\begingroup\$

Retina, 15 13 bytes

^(^1|\1\1)*1

Try it online!

Input and output in unary (the test suite includes conversion from and to decimal for convenience).

Explanation

This is quite easy to do in unary. All we want to do is delete the largest power of 2 from the input. We can match a power of 2 with some forward references. It's actually easier to match values of the form 2n-1, so we'll do that and match one 1 separately:

^(^1|\1\1)*1

The group 1 either matches a single 1 at the beginning to kick things off, or it matches twice what it did on the last iteration. So it matches 1, then 2, then 4 and so on. Since these get added up, we're always one short of a power of 2, which we fix with the 1 at the end.

Due the trailing linefeed, the match is simply removed from the input.

\$\endgroup\$
3
\$\begingroup\$

R, 28 bytes

function(x)x-2^(log2(x)%/%1)

Try it online!

Easiest to calculate the most significant bit via 2 ^ floor(log2(x)) rather than carry out base conversions, which are quite verbose in R

\$\endgroup\$
3
\$\begingroup\$

PARI/GP, 18 bytes

n->n-2^logint(n,2)

Alternate solution:

n->n-2^exponent(n)
\$\endgroup\$
  • \$\begingroup\$ The first one seems to give wrong answers. Should it be n->n-2^logint(n,2)? The second one is not supported in my version of PARI/GP, nor in the version used by tio.run. Is that a new function? \$\endgroup\$ – Jeppe Stig Nielsen Nov 15 '17 at 11:03
  • \$\begingroup\$ @JeppeStigNielsen Oops, fixed -- that's what I get for submitting from my phone. Yes, the second one is a new function. \$\endgroup\$ – Charles Nov 15 '17 at 16:36
  • \$\begingroup\$ @JeppeStigNielsen I just checked, exponent was added 5 days ago, compared to this challenge which was added yesterday. :) \$\endgroup\$ – Charles Nov 15 '17 at 16:38
3
\$\begingroup\$

Haskell, 32 29 bytes

(!1)
x!y|2*y>x=x-y|z<-2*y=x!z

Try it online!

-3 bytes thanks to @Laikoni

Older solution, 32 bytes

f x=last[x-2^i|i<-[0..x],2^i<=x]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Anonymous functions are allowed, so you don't need the f= in the first variant. Additionally z<-2*y=x!z saves a byte: Try it online! \$\endgroup\$ – Laikoni Nov 16 '17 at 14:42
3
\$\begingroup\$

Excel, 20 bytes

=A1-2^INT(LOG(A1,2))
\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! :) \$\endgroup\$ – DJMcMayhem Nov 16 '17 at 16:48
3
\$\begingroup\$

Excel, 36 31 bytes

-5 bytes thanks to @IanM_Matrix1

=BIN2DEC(MID(DEC2BIN(A1),2,99))

Nothing interesting.

\$\endgroup\$
  • \$\begingroup\$ Reduce the size to 31 bytes by replacing REPLACE with a MID: =BIN2DEC(MID(DEC2BIN(A1),2,99)) \$\endgroup\$ – IanM_Matrix1 Nov 16 '17 at 16:40

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.