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
    Nov 15, 2017 at 10:26
  • \$\begingroup\$ @clabacchio I.. it... er... wha? (nice one) \$\endgroup\$
    – Baldrickk
    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\$ Nov 16, 2017 at 18:54

79 Answers 79

1 2
3
1
\$\begingroup\$

Common Lisp, 40 bytes

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

Try it online!

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

\$\endgroup\$
5
  • \$\begingroup\$ You can get down to 48 bytes actually: $m=[math];$_-$m::pow(2,$m::floor($m::log($_,2))) \$\endgroup\$
    – cogumel0
    Nov 29, 2017 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\$ Nov 29, 2017 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, 2017 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, 2017 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\$ Nov 29, 2017 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]
\$\endgroup\$
1
\$\begingroup\$

Python, 32 bytes

lambda n:n-2**(n.bit_length()-1)
\$\endgroup\$
3
  • 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\$
    – DJMcMayhem
    Dec 11, 2017 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\$
    – DJMcMayhem
    Dec 11, 2017 at 22:01
  • 1
    \$\begingroup\$ @DJMcMayhem thanks for the courteous pointers. appreciate the gentle schooling \$\endgroup\$ Dec 11, 2017 at 22:02
1
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 74 65 bytes

	I =INPUT
	J =1
R	J =GE(I - J) J + J :S(R)
	OUTPUT =I - J / 2
END

Try it online!

	I =INPUT			;*read in input
	J =1				;*set J to 1
R	J =GE(I - J) J + J :S(R)	;*if I-J>=0, double J and repeat, otherwise
	OUTPUT =I - J / 2		;*output I-J/2
END
\$\endgroup\$
1
\$\begingroup\$

Python 2, 30 bytes

f=lambda n:n-1and 2*f(n/2)+n%2

Try it online!

Uses no built-in methods. 3 bytes longer than this solution using bin.

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

Pip, 8 bytes

FB+@>TBa

Try it online!

Explanation

     TBa  Convert cmdline arg to binary
   @>     Take all but the leftmost character
  +       Convert to number (required for turning "" into 0 so FB works properly)
FB        Convert from binary to decimal
\$\endgroup\$
1
\$\begingroup\$

Manufactoria, 24 Bytes, 3 Blocks

c12:6f3;c12:8f3;p12:7f2;

?lvl=32&code=c12:6f3;c12:8f3;p12:7f2;&ctm=Level_Name!;Level_description!;:*;5;3;0;
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 23 + 1 (-p) = 24 bytes

$_-=2**int((log)/log 2)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

GolfScript - 13 bytes

~2base(;2base

Explanation

~      # Parse argument
2base  # Convertion to base 2
(;     # Cut away first byte
2base  # Convertion from base 2
\$\endgroup\$
0
\$\begingroup\$

Tcl, 45 bytes

puts [scan [regsub 1 [format %b $argv] 0] %b]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 23 bytes

f=x=>x^1&&f(x/2)*2|x&1

Not the shortest JS solution overall, but it beats the .toString(2) solution.

\$\endgroup\$
0
\$\begingroup\$

C++, 63 bytes

[](decltype(0ul)x){auto y=x;return x^_BitScanReverse(&y,x)<<y;}

Usage (works in MS Visual Studio):

#include <intrin.h>
#include <stdio.h>

int main()
{
    auto h = [](decltype(0ul)x){auto y=x;return x^_BitScanReverse(&y,x)<<y;};

    printf("%d\n", h(10));
}

I added an artificial constraint on my code:

It must use _BitScanReverse

The effect this had on my code is quite severe.

  1. I used decltype(0ul) as an euphemism for unsigned long.
  2. _BitScanReverse outputs its result by pointer, so I had to declare another unsigned long variable. This time, I did it with auto y=x.
  3. The output of _BitScanReverse is "whether the input is nonzero", which is 1 (luckily).
  4. The returned expression modifies y and then uses it, which is Undefined Behavior. There are no warnings though, and it works correctly.
\$\endgroup\$
0
\$\begingroup\$

ARM (Thumb mode) machine code, 12 bytes

b0 fa 80 f1 01 31 88 40 c8 40 70 47

Disassembly:

fab0 f180       clz     r1, r0
3101            adds    r1, #1
4088            lsls    r0, r1
40c8            lsrs    r0, r1
4770            bx      lr
\$\endgroup\$
0
\$\begingroup\$

C++, 42 bytes

int f(int n){return n-exp2((int)log2(n));}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Could you provide a link to an online compiler where this works? I doubt this works without int n in the declaration, and I'm not sure that C++ has exp2 and log2 functions without some #include \$\endgroup\$
    – DJMcMayhem
    Nov 16, 2017 at 21:20
  • \$\begingroup\$ Added the return type. About the includes, I don't see them counted in any of the previous C/C++ replies and I don't see you downvoting them or hassling them about it. But thanks anyway. \$\endgroup\$
    – uKER
    Nov 16, 2017 at 21:26
  • 1
    \$\begingroup\$ Oh I didn't downvote you! I'm sorry if you got that impression. That's due to a bug that sometimes hits new users with short posts. Which is really unfortunate, but SE seems to not care. \$\endgroup\$
    – DJMcMayhem
    Nov 16, 2017 at 21:28
  • \$\begingroup\$ I see. No problem then. \$\endgroup\$
    – uKER
    Nov 16, 2017 at 21:31
  • 1
    \$\begingroup\$ In K&R C, any undeclared functions are assumed return an int, and take whatever type is passed in. Most modern compilers accept this, but create a warning. In golf we can make use of this. However, in your submission, you marked it as C++, not C. C++ does not allow undeclared functions. Also you are passing an int into exp2 (and log2), which won't be promoted to float. However, you can remove the int for the return and input for your function f - saving 8 bytes. This should work, for 50 bytes, when split over two lines #include<math.h> f(n){return n-exp2((int)log2(n));} \$\endgroup\$
    – CSM
    Nov 18, 2017 at 14:37
0
\$\begingroup\$

Pyth - 8 Bytes

ig.BQ2 2

Explanation:

ig.BQ2 2
i      2 Convert to base 2
 g   2   Slice from position 1 to the end (g slices from b-1)
  .B     Binary String representation of
    Q    Input
\$\endgroup\$
0
\$\begingroup\$

Fig, \$3\log_{256}(96)\approx\$ 2.469 bytes

Bpb

Try it online!

Same strategy as every other golflang.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 27 bytes

Just realized this is a port of @xnor's python2 answer.

f(n){n=n>1?2*f(n/2)+n%2:0;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Thunno 2, 5 bytes

ḃḣ0|Ḃ

Attempt This Online!

Explanation

ḃḣ0|Ḃ  # Implicit input      ->  100
ḃ      # Convert to binary   ->  "1100100"
 ḣ     # Remove first item   ->  "100100"
  0|   # Logical OR with 0   ->  "100100"
    Ḃ  # Convert to decimal  ->  36
       # Implicit output
\$\endgroup\$
1 2
3

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.