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\$
  • 19
    \$\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

3
\$\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.

|improve this answer|||||
\$\endgroup\$
2
\$\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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The () is apparently unnecessary \$\endgroup\$ – HyperNeutrino Nov 14 '17 at 19:16
  • \$\begingroup\$ 17 bytes \$\endgroup\$ – HyperNeutrino Nov 14 '17 at 19:16
  • 1
    \$\begingroup\$ 17 bytes: #-2^⌊Log2@#⌋& \$\endgroup\$ – J42161217 Nov 14 '17 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\$ – NieDzejkob Nov 14 '17 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\$ – Kelly Lowder Nov 14 '17 at 20:07
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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 % 2b, 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.
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Often assembly submissions are rated in the size of their assembled machine code output (which usually results in a way better score ;-) ) \$\endgroup\$ – Matteo Italia Nov 17 '17 at 14:31
  • \$\begingroup\$ @MatteoItalia that's something I'm going to look into then! \$\endgroup\$ – Alex Robinson Nov 17 '17 at 15:46
2
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ an explanation would be nice \$\endgroup\$ – Titus Nov 16 '17 at 11:52
  • \$\begingroup\$ Consider it done. \$\endgroup\$ – idrougge Nov 17 '17 at 16:48
2
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Julia, 24 bytes

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

Try it online!

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

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ – Laikoni Dec 17 '17 at 15:11
1
\$\begingroup\$

Pyth, 6 bytes

it.BQ2

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

CJam - 8 bytes

ri2b(;2b

Explanation

ri    # Reads input as integer
2b    # Convertion to base 2
(;    # Removes first element
2b    # Convertion from base 2
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace (;2 with (). \$\endgroup\$ – Martin Ender Nov 15 '17 at 8:40
  • \$\begingroup\$ @MartinEnder Thanks, great idea \$\endgroup\$ – FedeWar Nov 15 '17 at 9:56
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Ruby, 22 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Bash, 27 bytes

bc -l<<<"$1-2^(l($1)/l(2))"

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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;
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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 log2 built-in in C, I just (ab)used the fact that loge(x) / loge(2) = ln(x) / ln(2) = log2(x).


C (gcc), 34 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

PHP, 28 25+1 bytes

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

Run as pipe with -nF or try it online.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ -4 bytes by replacing &~ with ^. \$\endgroup\$ – Colera Su Nov 16 '17 at 23:36
  • 1
    \$\begingroup\$ @ColeraSu -3 bytes. +1 is for -F. But thanks. \$\endgroup\$ – Titus Nov 16 '17 at 23:44
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Well, there's a better way \$\endgroup\$ – NieDzejkob Nov 14 '17 at 19:49
  • \$\begingroup\$ “unfortunately” … err. 😉 \$\endgroup\$ – Konrad Rudolph Nov 15 '17 at 9:51
  • \$\begingroup\$ @KonradRudolph "unfortunately" in the sense that it stops me having a shorter answer :-P. Probably "fortunate" in every other use. \$\endgroup\$ – Ayb4btu Nov 15 '17 at 21:37
  • \$\begingroup\$ In the mathematical approach you can directly write System.Math.Log... and remove the using-Statement. \$\endgroup\$ – raznagul Nov 17 '17 at 11:39
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 40 bytes

(lambda(n)(- n(expt 2(floor(log n 2)))))

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Japt, 6 bytes

ì2 Åì2

Try it


Explanation

Convert to an array of base-2 digits with ì2, slice from the second element with Å and convert back to a base-10 integer with ì2.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 66 62 bytes

($c=[Convert])::ToInt32(0+($c::ToString("$args",2)|% su* 1),2)

Try it online!

Thanks to cogumel0 for -4 bytes.

Does exactly what it says on the tin. Takes input $args, converts it toString, replaces the leading 1 using System.substring, then converts it back toInt32. Output is implicit.

Yay for lengthy .NET calls.


Using the mathematical method that others are using, we can get down to

PowerShell, 59 56 bytes

param($a)$a-($m=[math])::pow(2,$m::floor($m::log($a,2)))

Try it online!

Thanks to cogumel0 for -3 bytes.

This takes input $a, takes the log in base 2, then floors that. The floor is needed because if we simply cast to an integer, PowerShell does Banker's Rounding which could lead to erroneous results. Then we take 2 to that power, and subtract that from $a. Output is implicit.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You can get down to 48 bytes actually: $m=[math];$_-$m::pow(2,$m::floor($m::log($_,2))) \$\endgroup\$ – cogumel0 Nov 29 '17 at 11:30
  • \$\begingroup\$ @cogumel0 That's using $_ for input, which I consider to be a snippet and not a function or program. The $m=[math] trick is pretty clever, though, thanks! \$\endgroup\$ – AdmBorkBork Nov 29 '17 at 13:19
  • \$\begingroup\$ Both filters and functions allow access to $_. But filters only have a Process block making them ideal for these scenarios. If you consider a function to be acceptable than so would a filter, and therefore this code is valid ;) \$\endgroup\$ – cogumel0 Nov 29 '17 at 13:37
  • \$\begingroup\$ You can also save a few more bytes on the first one too though: 61 bytes (even if you use $args instead of $_): $c=[Convert];$c::ToInt32(0+($c::ToString($args,2)|% su* 1),2). It uses string.Substring() instead of -replace, which shortens it somewhat. It does however need the 0+ to account for cases where the string has a length of 1 before you remove the first character (less bytes than doing [int]) \$\endgroup\$ – cogumel0 Nov 29 '17 at 13:43
  • \$\begingroup\$ But if using a filter, we'd need to have filter listed, which is going to be more bytes yet. Thanks for the substring idea, though, even though quotes around $args brings it up to 62. \$\endgroup\$ – AdmBorkBork Nov 29 '17 at 13:57
1
\$\begingroup\$

Add++, 24 14 bytes

D,f,@,BBEP2$Bb

Try it online!

How it works

D,f,@,   - Create a monadic function.
         - Example argument:   10
      BB - To binary; STACK = [[1 0 1 0]]
      EP - Dequeue;   STACK = [[0 1 0]]
      2  - Push 2;    STACK = [[0 1 0] 2]
      $  - Swap;      STACK = [2 [0 1 0]]
      Bb - From base; STACK = [2]
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Python, 32 bytes

lambda n:n-2**(n.bit_length()-1)
|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ Hello, and welcome to our site! There are a few things that this is missing. First off, you'll need to provide a byte count, which in this case is 25. But unfortunately, this breaks two of our standard rules: 1) This assumes that the input is stored in n, and 2) this simply evaluates to the answer rather than printing/returning it. You could fix this by taking input from STDIN (n=input();print(n-2**...) or by wrapping this in a function (def f(n):return n-2**... or lambda n:n-2**..., which is probably the best option). \$\endgroup\$ – James Dec 11 '17 at 22:01
  • \$\begingroup\$ Also, you could remove the spaces around the minus sign: n-2**(n.bit_length()-1) to save 2 bytes. \$\endgroup\$ – James Dec 11 '17 at 22:01
  • 1
    \$\begingroup\$ @DJMcMayhem thanks for the courteous pointers. appreciate the gentle schooling \$\endgroup\$ – ShpielMeister Dec 11 '17 at 22:02

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.