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

PARI/GP, 18 bytes

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

Alternate solution:

n->n-2^exponent(n)

• Jeppe Stig Nielsen: 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?
• Charles: @JeppeStigNielsen Oops, fixed -- that's what I get for submitting from my phone. Yes, the second one is a new function.
• Charles: @JeppeStigNielsen I just checked, exponent was added 5 days ago, compared to this challenge which was added yesterday. :)

Answer 2

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!

• Laikoni: 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!

Answer 3

QBIC, (削除) 26 (削除ここまで) 18 bytes

Thank you, @DLosc, for saving 8 bytes!

≈q*2<=:|q=q*2]?a-q

Explanation

≈ | WHILE
 q*2 q doubled (this doesn't actually double q, but evaluates 2q) 
 <= is less than or equal to
 : the input number (cmd line param, variable 'a')
q=q*2 double q (2, 4, 8, ...)
] WEND
?a-q PRINT a - q (ie 100 - 64 = 36)

Answer 4

Julia, 24 bytes

n->n-2^length(bin(n))÷2

Try it online!

Int(floor(log2(n))) is too long.

• Laikoni: Welcome to PPCG! :)

Answer 5

Ruby, 31 bytes

->n{(0..n).find{|i|n-i&n+~i<1}}

Another bit-twiddling approach, might work better in a language where 0 is falsey. Finds the smallest number i such that n-i is a power of two, using the property of powers of two that they're the only numbers with no 1 bits in common with their predecessors.

Answer 6

Befunge, 22 bytes

&:1\v\*2\<
$%.@>2/:#^_

Try it online!

Explanation

Befunge doesn't have bit manipulation instructions, but we can instead use the mod command (%) to mask out the bits that we want to keep. So basically we calculate n % 2^b, where b is the number of bits in the number minus one.

&: Read n from stdin and make a copy to work with.
 1\ Push the initial mask value below it on the stack.
 v Start a loop to determine the number of bits to mask.
 >2/ Divide the copy of n by 2.
 :#^_ Check if it has become zero.
 \< If not, turn back and swap the mask value to the top of the stack.
 *2 Multiply the mask value by 2.
 \ Swap the modified copy of n back to the top of the stack.
 ^ Repeat the loop.
$ Once the copy of n becomes zero, we can exit the loop and drop it.
 % We can then mod the original n with the mask value to get the result.
 .@ Finally output the result and exit.

Answer 7

IA-32 machine code, 12 bytes

Hexdump:

91 0f bd c8 33 d2 42 d3 e2 33 c2 c3

Corresponding assembly code, with inline disassembly:

91 xchg eax, ecx;
0f bd c8 bsr ecx, eax;
33 d2 xor edx, edx;
42 inc edx;
d3 e2 shl edx, cl;
33 c2 xor eax, edx;
c3 ret;

Answer 8

Motorola 68020 Assembler, Unknown byte count, possibly 8

BFFFO D0{31:32}, D1 # Scan D0 from MSB to LSB, looking for the first set bit,
 # from bit 31 for 32 bits
 # Store this in D1
BCLR D1, D0 # Clear the D1'th bit in D0

It's been a long time since I've done 680x0 assembler, and I can't find an online simulator. This takes a 32-bit input in D0, and returns it from there. It also trashes D1. Flags are also changed. Bad things will happen if D0 is zero; but the rules exclude that possibility.

Answer 9

16F48A Microcontroller, 155 bytes

IN Q,s0
MOVI s0,s1
MOVI s2,00
MOVI s3, 09
A: INC s2
SHR s1
JNZ A
B: DEC s3
DEC s1
JNZ B
C: MOVI s3,s4
SHL s0
DEC s3
JNZ C
D: DEC s4
SHR s0
JNZ D
OUT s0

explanation: This particular microcontroller takes inputs in binary, starting at the top of the code and working its way down. It can only use 9 registers (s0 through s8, but cannot output s8) and each of those registers can store 8 bits - again, in binary.

The first section takes the input and sets some values for later use.

section A shifts the input right, effectively removing bytes at the end, until it reaches zero, all the while, s2 is keeping track of how many shifts have taken place.

Section B then takes the amount of right shifts from 9, to determine how many times to shift left until the front byte that is a 1 has been removed.

Section C actually shifts left, but saves the amount of shifts to be able to shift right again.

Finally, section D shifts it right, to move it to the original position, minus the first 1.

• Matteo Italia: Often assembly submissions are rated in the size of their assembled machine code output (which usually results in a way better score ;-) )
• Alex Robinson: @MatteoItalia that's something I'm going to look into then!

Answer 10

REXX, 52 bytes

b=x2b(d2x(arg(1)))
parse var b '1' b
say x2d(b2x(b))

Explanation:

1. Convert argument 1 into hex, then into binary representation.
2. Use parse to find first '1' in b, then store the rest of the string in b again.
3. Convert b into hex, then into decimal.

• Titus: an explanation would be nice
• idrougge: Consider it done.

Answer 11

J, 8 Bytes

#.@}.@#:

How it works:

 @ @ | Verb conjunction. Makes sure it isn’t executed as a hook
 #: | Converts Number to binary, with no leading 0s (except if arg is 0)
 }. | Drop leading 1
#. | Convert back to int 

Works for 1 and 0 since #. will convert an empty array into 0

Answer 12

Japt, (削除) 6 (削除ここまで) 4 bytes

ì2_Å

Try it or run all test cases

ì2_Å :Implicit input of integer
ì2 :Convert to base 2 digit array
 _ :Pass through the following function and convert back to decimal
 Å : Slice off the first digit

Answer 13

Vyxal, 3 bytes

bḢB

Try it Online!

Explained

bḢB
b # binary
 Ḣ # remove first item
 B # binary back to base 10

Answer 14

Pyth, 6 bytes

it.BQ2

Try it online!

• Steven H.: -1 bytes

Answer 15

Actually, 7 bytes

;╘L2n@-

Try it online!

Answer 16

05AB1E, 7 bytes

bS1 ̧-JC

Try it online! or Try all test cases

b # Convert to binary
 S # Split
 1 ̧- # Subtract 1 from the first element
 JC # Join and convert to decimal

---

b¦C works except for an input of 1

• Mr. Xcoder: The logarithm version is a bit shorter, too bad we need to handle 1 though :(, otherwise the 3-byter would be the shortest
• Maya: @Mr.Xcoder the answer that you've linked doesn't look like it's using logarithms. However, the formula n-2^floor(log2(n)) handles 1 correctly, if that's what you are referring to
• Mr. Xcoder: @NieDzejkob The answer I linked to is my own answer and does use logarithms.
• Maya: @Mr.Xcoder then the StackExchange app is utterly broken, let me see

Answer 17

Octave, 26 bytes

@(x)bi2de(de2bi(x)(2:end))

Try it online!

Note: The TIO-link uses dec2bin and bin2dec instead of de2bi and bi2de, because the communications package is not installed. The code works fine on Octave-online.net.

Explanation:

@(x) % Anonymous function that takes a decimal number x as input
 bi2de( % Convert the following to decimal:
 de2bi(x) % Convert x to decimal
 (2:end) % And take all elements except the first
 ) % That's it.

Answer 18

Perl 6, 17 bytes

{$_+&+^(1+<.msb)}

Try it online!

• $_ is the argument to the function.
• +& is the bitwise AND operator.
• +^ is the bitwise NOT operator.
• +< is the bitwise left shift operator.
• .msb returns the most significant bit of the function argument.

Answer 19

CJam - 8 bytes

ri2b(;2b

Explanation

ri # Reads input as integer
2b # Convertion to base 2
(; # Removes first element
2b # Convertion from base 2

• Martin Ender: You can replace (;2 with ().
• FedeWar: @MartinEnder Thanks, great idea

Answer 20

Batch, 62 bytes

@set/an=%2+%2+1
@if %1 gtr %n% %0 %1 %n%
@cmd/cset/a%1-n/2-1

Edged out this 63-byte attempt:

@set/an=%2+%2+1,m=%1^^n+1
@if %m% gtr %n% %0 %1 %n%
@echo %m%

Which itself edged out this 64-byte port:

@set n=1
:l
@if %1 geq %n% set/an*=2&goto l
@cmd/cset/a%1-n/2

Answer 21

Funky, (削除) 23 (削除ここまで) 20 bytes

n=>n~1<<math.log(2n)

(削除) I'm quite pleased with the result of this one.

Firstly, this calculates math.floor(math.log(2,n)) incrementing a variable i whilst dividing n by two until it is <1. Then, get's two to the power of that value, which removes all but the most significant bit from n. We can then get the answer by xoring this with n, which in funky is done with ~. (削除ここまで)

Turns out the Javascript method works for this too, although math.log2 can be replaced with math.log(2, because 2 and n are seen as two separate tokens in Funky, and thus is parsed like 2, n

Try it online!

Answer 22

Ruby, 22 bytes

->n{n^1<<Math.log2(n)}

Try it online!

Answer 23

Brain-Flak, 44 bytes

<>(()){((({}{}))){<>({}[()])}{}}<>([{}]{}<>)

Try it online!

Explanation

The bulk of the modulus program is {(({})){<>({}[()])}{}}, which decrements two counters and resets the base counter every time it reaches zero. To deal with powers of two, the counter needs to be doubled each time it resets. The obvious way to do that is by replacing (({})) with ((({}){})), but this won't work since the doubling happens before the first iteration.

Instead, ((({}{}))) pushes the initial counter an additional time, and then adds these two copies together in the next iteration. In the first iteration, a 1 and an implicit 0 are added together to start with 1 as desired.

Answer 24

Bash, 27 bytes

bc -l<<<"1ドル-2^(l(1ドル)/l(2))"

Try it online!

Answer 25

C (gcc), 37 + 2 (-lm) = 39 bytes

f(x){x-=pow(2,floor(log(x)/log(2)));}

Try it online!

Saved some bytes thanks to a tip pointed out by @JustinMariner! This is my first proper C golf :-)

Since there is no plain log₂ built-in in C, I just (ab)used the fact that log_e(x) / log_e(2) = ln(x) / ln(2) = log₂(x).

---

C (gcc), 34 bytes

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

Try it online!

• Justin Mariner: I think you can save some bytes by using this tip: Try it online!

Answer 26

PHP, (削除) 28 (削除ここまで) 25+1 bytes

<?=$argn^1<<log($argn,2);

Run as pipe with -nF or try it online.

• Colera Su: -4 bytes by replacing &~ with ^.
• Titus: @ColeraSu -3 bytes. +1 is for -F. But thanks.

Answer 27

PHP, 38 bytes

<?=bindec(substr(decbin($argv[1]),1));

Straightforward way to do it. Convert the input to binary, remove the first character of the "string", convert back to decimal.

Try it online!

Answer 28

C# (.NET Core), (削除) 28+13=41 (削除ここまで) 35 bytes

n=>n-(1<<(int)System.Math.Log(n,2))

Try it online!

Acknowledgements

All credit for this answer goes to NieDzejkob; the mathematical approach is significantly better than binary string manipulation (below).

-6 bytes thanks @raznagul for seeing that System could just be included directly in the code, rather than as using System;.

C# (.NET Core), 86+13=99 bytes

n=>{var t=Convert.ToString(n,2).Remove(0,1);return t.Length<1?0:Convert.ToInt32(t,2);}

Try it online!

+13 bytes for using System;

UnGolfed

n=>{
 var t = Convert.ToString(n,2).Remove(0,1); 
 return t.Length < 1 ? 0
 : Convert.ToInt32(t,2);
}

Unfortunately Convert.ToInt32 throws an exception on "", instead of returning 0.

• Maya: Well, there's a better way
• Konrad Rudolph: "unfortunately" ... err. 😉
• Ayb4btu: @KonradRudolph "unfortunately" in the sense that it stops me having a shorter answer :-P. Probably "fortunate" in every other use.
• raznagul: In the mathematical approach you can directly write System.Math.Log... and remove the using-Statement.

Answer 29

Jq 1.5, 19 bytes

.-pow(2;log2|floor)

This is just a jq version of the formula n - 2^Floor[Log2[n]] from OEIS A053645

Try it online!

Answer 30

C 35 bytes

N;f(n){for(N=n;n&n-1;)n&=n-1;N-=n;}

Try it online!

n&=n-1

Does the opposite of the problem statement, it clears the least significant bit.
I have a vague memory of there being a similar trick for most significant bit from seeing it on coding game but may remember wrong.

Recursive function, (削除) 45 (削除ここまで) 43 bytes

N;g(n){n&=(N=n&~-n)?g(N):n;}f(n){N=n-g(n);}

Try it online!

cleblancs code shortened to 34 bytes

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

Try it online!

28 bytes, possibly cheating , using pointer instead of return

f(*n){*n^=1<<(int)log2(*n);}

Try it on ideone! , doesn't work on tio.run