Clearing the most significant bit from an integer

Question

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.

• clabacchio: Clearing the most significant bit from 10 obviously gives 0 :D
• Baldrickk: @clabacchio I.. it... er... wha? (nice one)
• Michael Kay: 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".

Answer 1

C (gcc), (削除) 49 (削除ここまで) (削除) 44 (削除ここまで) (削除) 40 (削除ここまで) 39 bytes

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

Try it online!

• hyperneutrino: 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.
• cleblanc: @HyperNeutrino I saw and approved the edit just now. Wasn't aware of that rule but it's a nice golfing tip!
• hyperneutrino: 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. :)

Answer 2

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!

Answer 3

05AB1E, 5 bytes

.2ó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 - 2^{floor(log₂N)}:

• .2 - Logarithm with base 2.
• ó - Floor to an integer.
• o - 2 raised to the power of the result above.
• - - Difference.

• Magic Octopus Urn: b¦C also works... doesn't it? Convert to binary, MSB is always at index 1, remove MSB, convert back.
• Mr. Xcoder: @MagicOctopusUrn No that is wrong, fails for 1!
• Kevin Cruijssen: @MagicOctopusUrn b¦C works for 1 in the new 05AB1E version. Although I like your .²óo- more tbh. :)

Answer 4

Jelly, 3 bytes

BḊḄ

Try it online!

Explanation

BḊḄ Main Link
B Convert to binary
 Ḋ Dequeue; remove the first element
 Ḅ Convert from binary

• Bartek Banachewicz: Aren't Ḅ and Ḋ two-byte codepoints? This would change the overall size to 5 bytes.
• steenbergh: @BartekBanachewicz Jelly uses its own codepage, where those chars are only 1 byte.
• Ukko: Thanks for asking and answering this, that has bugged me for a long time!

Answer 5

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.

• ETHproductions: Welcome to PPCG, and great first answer! We hope you'll enjoy participating in many more challenges :-)
• Steadybox: You don't need a full program with main, a function is a valid submission. Changing this into a function and taking input as an argument to said function saves 18 bytes.
• Steadybox: You could even write it as a macro to save two more bytes.

Answer 6

Java (OpenJDK 8), 23 bytes

n->n^n.highestOneBit(n)

Try it online!

Sorry, built-in :-/

• Kevin Cruijssen: 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
• Olivier Grégoire: @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
• Kevin Cruijssen: 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.
• JollyJoker: I was going to post the same, only minus instead of xor. Remembered the method from this
• Olivier Grégoire: @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 ;-)

Answer 7

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

• Sanchises: 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)

Answer 8

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

• Bartek Banachewicz: Similarly to the Jelly solution, this seems like it's actually 5 bytes, not 3.
• hyperneutrino: @BartekBanachewicz Similarly to Jelly, Husk uses its own codepage, so this is actually 3 bytes :P
• Laikoni: @BartekBanachewicz See here for the codepage: github.com/barbuz/Husk/wiki/Codepage

Answer 9

Ohm v2, 3 bytes

b(ó

Try it online!

Answer 10

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

• totallyhuman: ...Just when I was working the bitwise math out. :P
• hyperneutrino: @totallyhuman heh sorry but beat you to it :P
• user45941: 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).
• hyperneutrino: @Mego Cool, thanks for the addition!

Answer 11

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!

• caird coinheringaahing: Why not lambda n:int(bin(n)[3:],2)?
• totallyhuman: 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!
• caird coinheringaahing: I've edited the code so that it works, (and saves 4 bytes)
• totallyhuman: That still errors on 1.
• FlipTack: @cairdcoinheringaahing That was my original answer, but then I realised it errored on 1. The workaround ends up longer than a simple XOR method

Answer 12

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

Answer 13

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.

Answer 14

Mathematica, 37 bytes

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

Try it online!

Answer 15

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!

• ETHproductions: why would you do .slice`1`^0 when .slice(1)^0 would work just as well, haha
• user72349: @ETHproductions. This one looks better :)

Answer 16

J, 6 bytes

}.&.#:

Pretty simple.

Explanation

}.&.#:
 #: convert to list of binary digits
 &. apply right function, then left, then the inverse of right
}. behead

• Cyoce: I was going to post this :(
• Adám: @Cyoce Me too...

Answer 17

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

Answer 18

Ruby, 26 bytes

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

->n{/./=~'%b'%n;$'.to_i 2}

• Ventero: 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}
• histocrat: ->n{/./=~'%b'%n;$'.to_i 2}
• shashwat: @Ventero -1 is not required: ->n{n.to_s(2)[1..].to_i 2}

Answer 19

C (gcc), 38 bytes

Built-in in gcc used.

f(c){return c^1<<31-__builtin_clz(c);}

• user72349: Replacing 31- with ~ should save two bytes.
• Colera Su: @ThePirateBay it depends on hardware whether the shift is masked. On my computer, it will output 0.

Answer 20

Excel, 20 bytes

=A1-2^INT(LOG(A1,2))

• DJMcMayhem: Welcome to the site! :)

Answer 21

Excel, (削除) 36 (削除ここまで) 31 bytes

-5 bytes thanks to @IanM_Matrix1

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

Nothing interesting.

• IanM_Matrix1: Reduce the size to 31 bytes by replacing REPLACE with a MID: =BIN2DEC(MID(DEC2BIN(A1),2,99))
• General Grievance: Save a byte: BASE(A1,2) instead of DEC2BIN(A1)
• Wernisch: @Calculuswhiz, I use Office 2010, which does not support BASE.

Answer 22

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

• Ruslan: 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.
• Michael Dorgan: 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.
• Michael Dorgan: Funny thing, i can do it in 1 less operation, but I the byte size goes up by 2. Ah code golf.

Answer 23

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

Answer 24

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.

Answer 25

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.

• hyperneutrino: The () is apparently unnecessary
• hyperneutrino: 17 bytes
• ZaMoC: 17 bytes: #-2^⌊Log2@#⌋&
• Maya: @Jenny_mathy Someone came up with the same exact program? I didn't know this was a sequence in OEIS
• Kelly Lowder: 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.

Answer 26

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

Answer 27

Octave, 20 bytes

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

Try it online!

Answer 28

APL (Dyalog Unicode), 9 bytes

⊢-2*∘⌊2⍟⊢

Try it online!

-1 byte thanks to Adam

• Adám: Completely correct, although I would have used TIO to generate a template for me. Anyway, ⊢-2*∘⌊2⍟⊢ saves a byte.
• cmm: I was sad that APL wasn't represented, and there is was, almost lost in the scroll! I miss APL.
• Adám: @cmm APL is alive and well. Feel free to hang out in the Stack Exchange APL chat room.

Answer 29

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}.

Answer 30

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 2ⁿ-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.