Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
The input is a single positive integer n
The output isn with its most significant bit set to 0.
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.
n->n-2^logint(n,2)
Alternate solution:
n->n-2^exponent(n)
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\$
Nov 15, 2017 at 11:03
exponent was added 5 days ago, compared to this challenge which was added yesterday. :)
\$\endgroup\$
(!1)
x!y|2*y>x=x-y|z<-2*y=x!z
-3 bytes thanks to @Laikoni
f x=last[x-2^i|i<-[0..x],2^i<=x]
f= in the first variant. Additionally z<-2*y=x!z saves a byte: Try it online!
\$\endgroup\$
Thank you, @DLosc, for saving 8 bytes!
≈q*2<=:|q=q*2]?a-q
≈ | 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)
->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.
&:1\v\*2\<
$%.@>2/:#^_
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.
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;
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.
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.
b=x2b(d2x(arg(1)))
parse var b '1' b
say x2d(b2x(b))
Explanation:
b, then store the rest of the string in b again.b into hex, then into decimal.
#.@}.@#:
@ @ | 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
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
1 though :(, otherwise the 3-byter would be the shortest
\$\endgroup\$
Nov 14, 2017 at 20:04
n-2^floor(log2(n)) handles 1 correctly, if that's what you are referring to
\$\endgroup\$
@(x)bi2de(de2bi(x)(2:end))
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.
@(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.
{$_+&+^(1+<.msb)}
$_ 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.
ri2b(;2b
ri # Reads input as integer
2b # Convertion to base 2
(; # Removes first element
2b # Convertion from base 2
@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
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
<>(()){((({}{}))){<>({}[()])}{}}<>([{}]{}<>)
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.
-lm) = 39 bytesf(x){x-=pow(2,floor(log(x)/log(2)));}
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).
f(c){c-=c^1<<31-__builtin_clz(c);}
-F. But thanks.
\$\endgroup\$
<?=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.
n=>n-(1<<(int)System.Math.Log(n,2))
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;.
n=>{var t=Convert.ToString(n,2).Remove(0,1);return t.Length<1?0:Convert.ToInt32(t,2);}
+13 bytes for using System;
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.
System.Math.Log... and remove the using-Statement.
\$\endgroup\$
.-pow(2;log2|floor)
This is just a jq version of the formula n - 2^Floor[Log2[n]] from OEIS A053645
N;f(n){for(N=n;n&n-1;)n&=n-1;N-=n;}
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);}
cleblancs code shortened to 34 bytes
i=1;f(n){for(;n/i/2;i*=2);n-=n^i;}
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
10obviously gives0:D \$\endgroup\$