33
\$\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\$
3
  • 22
    \$\begingroup\$ Clearing the most significant bit from 10 obviously gives 0 :D \$\endgroup\$
    – clabacchio
    Commented Nov 15, 2017 at 10:26
  • \$\begingroup\$ @clabacchio I.. it... er... wha? (nice one) \$\endgroup\$
    – Baldrickk
    Commented Nov 15, 2017 at 10:46
  • 14
    \$\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\$ Commented Nov 16, 2017 at 18:54

79 Answers 79

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\$
3
  • 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\$
    – hyper-neutrino
    Commented Nov 15, 2017 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
    Commented Nov 15, 2017 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\$
    – hyper-neutrino
    Commented Nov 15, 2017 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\$
10
\$\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\$
3
  • 2
    \$\begingroup\$ b¦C also works... doesn't it? Convert to binary, MSB is always at index 1, remove MSB, convert back. \$\endgroup\$ Commented Nov 15, 2017 at 12:01
  • 3
    \$\begingroup\$ @MagicOctopusUrn No that is wrong, fails for 1! \$\endgroup\$
    – Mr. Xcoder
    Commented Nov 15, 2017 at 12:15
  • \$\begingroup\$ @MagicOctopusUrn b¦C works for 1 in the new 05AB1E version. Although I like your .²óo- more tbh. :) \$\endgroup\$ Commented Sep 22, 2022 at 14:05
9
\$\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\$
3
  • 2
    \$\begingroup\$ Aren't and two-byte codepoints? This would change the overall size to 5 bytes. \$\endgroup\$ Commented Nov 15, 2017 at 12:30
  • 3
    \$\begingroup\$ @BartekBanachewicz Jelly uses its own codepage, where those chars are only 1 byte. \$\endgroup\$
    – steenbergh
    Commented Nov 15, 2017 at 12:53
  • 1
    \$\begingroup\$ Thanks for asking and answering this, that has bugged me for a long time! \$\endgroup\$
    – Ukko
    Commented Nov 15, 2017 at 15:08
9
\$\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\$
3
8
\$\begingroup\$

Java (OpenJDK 8), 23 bytes

n->n^n.highestOneBit(n)

Try it online!

Sorry, built-in :-/

\$\endgroup\$
5
  • \$\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\$ Commented Nov 15, 2017 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\$ Commented Nov 15, 2017 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\$ Commented Nov 16, 2017 at 7:57
  • 2
    \$\begingroup\$ I was going to post the same, only minus instead of xor. Remembered the method from this \$\endgroup\$
    – JollyJoker
    Commented Nov 16, 2017 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\$ Commented Nov 16, 2017 at 8:41
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
  • 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
    Commented Nov 15, 2017 at 9:19
7
\$\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\$
3
  • \$\begingroup\$ Similarly to the Jelly solution, this seems like it's actually 5 bytes, not 3. \$\endgroup\$ Commented Nov 15, 2017 at 12:31
  • 1
    \$\begingroup\$ @BartekBanachewicz Similarly to Jelly, Husk uses its own codepage, so this is actually 3 bytes :P \$\endgroup\$
    – hyper-neutrino
    Commented Nov 15, 2017 at 13:00
  • \$\begingroup\$ @BartekBanachewicz See here for the codepage: github.com/barbuz/Husk/wiki/Codepage \$\endgroup\$
    – Laikoni
    Commented Nov 15, 2017 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\$
4
  • \$\begingroup\$ ...Just when I was working the bitwise math out. :P \$\endgroup\$ Commented Nov 14, 2017 at 19:05
  • \$\begingroup\$ @totallyhuman heh sorry but beat you to it :P \$\endgroup\$
    – hyper-neutrino
    Commented Nov 14, 2017 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\$
    – user45941
    Commented Nov 14, 2017 at 19:08
  • \$\begingroup\$ @Mego Cool, thanks for the addition! \$\endgroup\$
    – hyper-neutrino
    Commented Nov 14, 2017 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\$
5
  • \$\begingroup\$ Why not lambda n:int(bin(n)[3:],2)? \$\endgroup\$ Commented Nov 14, 2017 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\$ Commented Nov 14, 2017 at 21:06
  • \$\begingroup\$ I've edited the code so that it works, (and saves 4 bytes) \$\endgroup\$ Commented Nov 14, 2017 at 21:07
  • \$\begingroup\$ That still errors on 1. \$\endgroup\$ Commented Nov 14, 2017 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
    Commented Nov 14, 2017 at 21:52
5
\$\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\$
5
\$\begingroup\$

32-bit x86 assembler, 10 9 7 bytes

Byte code:

0F BD C8 0F B3 C8 C3

Disassembly:

bsr ecx, eax
btr eax, ecx
ret

accepts and returns the value in the eax register.

Perform a reverse scan for the first set bit, and then reset that bit.

\$\endgroup\$
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\$
2
  • \$\begingroup\$ why would you do .slice`1`^0 when .slice(1)^0 would work just as well, haha \$\endgroup\$ Commented Nov 15, 2017 at 0:19
  • \$\begingroup\$ @ETHproductions. This one looks better :) \$\endgroup\$
    – user72349
    Commented Nov 15, 2017 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\$
2
  • \$\begingroup\$ I was going to post this :( \$\endgroup\$
    – Cyoce
    Commented Nov 15, 2017 at 6:07
  • \$\begingroup\$ @Cyoce Me too... \$\endgroup\$
    – Adám
    Commented Nov 15, 2017 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\$
3
  • \$\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
    Commented Nov 14, 2017 at 21:37
  • \$\begingroup\$ ->n{/./=~'%b'%n;$'.to_i 2} \$\endgroup\$
    – histocrat
    Commented Nov 14, 2017 at 23:11
  • \$\begingroup\$ @Ventero -1 is not required: ->n{n.to_s(2)[1..].to_i 2} \$\endgroup\$
    – shashwat
    Commented Mar 15, 2020 at 16:24
4
\$\begingroup\$

C (gcc), 38 bytes

Built-in in gcc used.

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

Excel, 20 bytes

=A1-2^INT(LOG(A1,2))
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to the site! :) \$\endgroup\$
    – DJMcMayhem
    Commented Nov 16, 2017 at 16:48
4
\$\begingroup\$

Excel, 36 31 bytes

-5 bytes thanks to @IanM_Matrix1

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

Nothing interesting.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Reduce the size to 31 bytes by replacing REPLACE with a MID: =BIN2DEC(MID(DEC2BIN(A1),2,99)) \$\endgroup\$ Commented Nov 16, 2017 at 16:40
  • \$\begingroup\$ Save a byte: BASE(A1,2) instead of DEC2BIN(A1) \$\endgroup\$ Commented Nov 24, 2020 at 13:45
  • \$\begingroup\$ @Calculuswhiz, I use Office 2010, which does not support BASE. \$\endgroup\$
    – Wernisch
    Commented Mar 10, 2021 at 15:16
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\$
3
  • \$\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
    Commented Nov 16, 2017 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\$ Commented Nov 17, 2017 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\$ Commented Nov 20, 2017 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\$

Mathematica, 21 17 bytes

#-2^Floor@Log2@#&

Try it online!

This is my first Mathematica answer, feel free to tell me what have I screwed up.

-4 bytes thanks to @HyperNeutrino!

So as it turns out, someone made a similar program before, and sent it to the OEIS. However, keep in mind that the floor of a logarithm is basically defined as the number of digits of a number. This is just a coincidence, or rather a task simple enough that many people will get the same answer.

\$\endgroup\$
10
  • \$\begingroup\$ The () is apparently unnecessary \$\endgroup\$
    – hyper-neutrino
    Commented Nov 14, 2017 at 19:16
  • \$\begingroup\$ 17 bytes \$\endgroup\$
    – hyper-neutrino
    Commented Nov 14, 2017 at 19:16
  • 1
    \$\begingroup\$ 17 bytes: #-2^⌊Log2@#⌋& \$\endgroup\$
    – ZaMoC
    Commented Nov 14, 2017 at 19:33
  • \$\begingroup\$ @Jenny_mathy Someone came up with the same exact program? I didn't know this was a sequence in OEIS \$\endgroup\$
    – Maya
    Commented Nov 14, 2017 at 19:58
  • 1
    \$\begingroup\$ Too bad we can't do #~BitClear~-1& which would be 14 bytes. Seems like the natural extension of the syntax. Maybe in version 12. \$\endgroup\$ Commented Nov 14, 2017 at 20:07
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\$
3
  • \$\begingroup\$ Completely correct, although I would have used TIO to generate a template for me. Anyway, ⊢-2*∘⌊2⍟⊢ saves a byte. \$\endgroup\$
    – Adám
    Commented Nov 14, 2017 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
    Commented Nov 15, 2017 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
    Commented Nov 15, 2017 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\$

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.