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

3
\$\begingroup\$

PARI/GP, 18 bytes

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

Alternate solution:

n->n-2^exponent(n)
\$\endgroup\$
3
  • \$\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\$ Commented Nov 15, 2017 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
    Commented Nov 15, 2017 at 16:36
  • \$\begingroup\$ @JeppeStigNielsen I just checked, exponent was added 5 days ago, compared to this challenge which was added yesterday. :) \$\endgroup\$
    – Charles
    Commented Nov 15, 2017 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
  • 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
    Commented Nov 16, 2017 at 14:42
3
\$\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)
\$\endgroup\$
0
3
\$\begingroup\$

Julia, 24 bytes

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

Try it online!

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

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$
    – Laikoni
    Commented Dec 17, 2017 at 15:11
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.

\$\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.
\$\endgroup\$
2
\$\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;
\$\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.

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

\$\endgroup\$
2
  • 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\$ Commented Nov 17, 2017 at 14:31
  • \$\begingroup\$ @MatteoItalia that's something I'm going to look into then! \$\endgroup\$ Commented Nov 17, 2017 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.
\$\endgroup\$
2
  • \$\begingroup\$ an explanation would be nice \$\endgroup\$
    – Titus
    Commented Nov 16, 2017 at 11:52
  • \$\begingroup\$ Consider it done. \$\endgroup\$
    – idrougge
    Commented Nov 17, 2017 at 16:48
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 3 bytes

bḢB

Try it Online!

Explained

bḢB
b   # binary
 Ḣ  # remove first item
  B # binary back to base 10
\$\endgroup\$
1
\$\begingroup\$

Pyth, 6 bytes

it.BQ2

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ -1 bytes \$\endgroup\$
    – Steven H.
    Commented Nov 14, 2017 at 19:25
1
\$\begingroup\$

Actually, 7 bytes

;╘L2ⁿ@-

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ The logarithm version is a bit shorter, too bad we need to handle 1 though :(, otherwise the 3-byter would be the shortest \$\endgroup\$
    – Mr. Xcoder
    Commented Nov 14, 2017 at 20:04
  • \$\begingroup\$ @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 \$\endgroup\$
    – Maya
    Commented Nov 14, 2017 at 20:22
  • \$\begingroup\$ @NieDzejkob The answer I linked to is my own answer and does use logarithms. \$\endgroup\$
    – Mr. Xcoder
    Commented Nov 14, 2017 at 20:24
  • \$\begingroup\$ @Mr.Xcoder then the StackExchange app is utterly broken, let me see \$\endgroup\$
    – Maya
    Commented Nov 14, 2017 at 20:25
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.
\$\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.
\$\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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can replace (;2 with (). \$\endgroup\$ Commented Nov 15, 2017 at 8:40
  • \$\begingroup\$ @MartinEnder Thanks, great idea \$\endgroup\$
    – FedeWar
    Commented Nov 15, 2017 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
\$\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!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 22 bytes

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

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

Bash, 27 bytes

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

Try it online!

\$\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!

\$\endgroup\$
1
1
\$\begingroup\$

PHP, 28 25+1 bytes

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

Run as pipe with -nF or try it online.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -4 bytes by replacing &~ with ^. \$\endgroup\$
    – Colera Su
    Commented Nov 16, 2017 at 23:36
  • 1
    \$\begingroup\$ @ColeraSu -3 bytes. +1 is for -F. But thanks. \$\endgroup\$
    – Titus
    Commented Nov 16, 2017 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!

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

\$\endgroup\$
4
  • \$\begingroup\$ Well, there's a better way \$\endgroup\$
    – Maya
    Commented Nov 14, 2017 at 19:49
  • \$\begingroup\$ “unfortunately” … err. 😉 \$\endgroup\$ Commented Nov 15, 2017 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
    Commented Nov 15, 2017 at 21:37
  • \$\begingroup\$ In the mathematical approach you can directly write System.Math.Log... and remove the using-Statement. \$\endgroup\$
    – raznagul
    Commented Nov 17, 2017 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!

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

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