Clearing the most significant bit from an integer

29

2

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.

Marcus Andrews

Posted 2017-11-14T18:59:57.710

Reputation: 446

19Clearing the most significant bit from 10 obviously gives 0 :D – clabacchio – 2017-11-15T10:26:02.947

@clabacchio I.. it... er... wha? (nice one) – Baldrickk – 2017-11-15T10:46:04.663

12It 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". – Michael Kay – 2017-11-16T18:54:45.940

Answers

12

C (gcc), 49 44 40 39 bytes

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

Try it online!

cleblanc

Posted 2017-11-14T18:59:57.710

Reputation: 3 360

1You can replace i<=n with n/i for -1 byte. This isn't my golf, someone else tried to edit it into your post but I rolled it back because edits for golfing posts are not accepted according to our community rules. – HyperNeutrino – 2017-11-15T13:54:55.593

1@HyperNeutrino I saw and approved the edit just now. Wasn't aware of that rule but it's a nice golfing tip! – cleblanc – 2017-11-15T13:55:55.030

Ah okay. Yeah typically people are supposed to post comments for golfing tips and OP should make the edits, but if you accepted it, it's not really as much of a problem. :) – HyperNeutrino – 2017-11-15T13:56:37.870

10

Python 2, 27 bytes

lambda n:n^2**len(bin(n))/8

Try it online!

26 bytes

Unfortunately, this does not work for 1:

lambda n:int(bin(n)[3:],2)

Try it online!

FlipTack

Posted 2017-11-14T18:59:57.710

Reputation: 13 242

9

05AB1E, 5 bytes

.²óo-

Try it online!

Removing the most significant bit from an integer N is equivalent to finding the distance from N to the highest integer power of 2 lower than N.

Thus, I used the formula N - 2floor(log2N):

  • - Logarithm with base 2.
  • ó - Floor to an integer.
  • o - 2 raised to the power of the result above.
  • - - Difference.

Mr. Xcoder

Posted 2017-11-14T18:59:57.710

Reputation: 39 774

1b¦C also works... doesn't it? Convert to binary, MSB is always at index 1, remove MSB, convert back. – Magic Octopus Urn – 2017-11-15T12:01:45.213

2@MagicOctopusUrn No that is wrong, fails for 1! – Mr. Xcoder – 2017-11-15T12:15:17.593

8

Jelly, 3 bytes

BḊḄ

Try it online!

Explanation

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary

HyperNeutrino

Posted 2017-11-14T18:59:57.710

Reputation: 26 575

2Aren't and two-byte codepoints? This would change the overall size to 5 bytes. – Bartek Banachewicz – 2017-11-15T12:30:28.123

3

@BartekBanachewicz Jelly uses its own codepage, where those chars are only 1 byte.

– steenbergh – 2017-11-15T12:53:58.613

1Thanks for asking and answering this, that has bugged me for a long time! – Ukko – 2017-11-15T15:08:33.870

8

C (gcc) -- 59 bytes

main(i){scanf("%d",&i);return i&~(1<<31-__builtin_clz(i));}

This gcc answer uses only integer bitwise and arithmetic operations. No logarithms here! It may have issues with an input of 0, and is totally non-portable.

It's my first answer on this site, so I'd love feedback and improvements. I sure had fun with learning bitwise expressions.

Charles Diploma

Posted 2017-11-14T18:59:57.710

Reputation: 81

1Welcome to PPCG, and great first answer! We hope you'll enjoy participating in many more challenges :-) – ETHproductions – 2017-11-15T03:53:12.233

You don't need a full program with main, a function is a valid submission. Changing this into a function and taking input as an argument to said function saves 18 bytes.

– Steadybox – 2017-11-17T16:16:20.910

1

You could even write it as a macro to save two more bytes.

– Steadybox – 2017-11-17T16:19:46.103

7

MATL, 8 6 bytes

B0T(XB

Try it online!

Saved two bytes thanks to Cinaski. Switching to assignment indexing instead of reference indexing was 2 bytes shorter :)

Explanation:

          % Grab input implicitly: 267
B         % Convert to binary: [1 0 0 0 0 1 0 1 1]
 0T(      % Set the first value to 0: [0 0 0 0 0 1 0 1 1]
    XB    % Convert to decimal: 11

Stewie Griffin

Posted 2017-11-14T18:59:57.710

Reputation: 43 471

1You could have used reference indexing (also for 6 bytes), if you used 4L rather than [2J]. Another fun 6 bytes: tZlcW- (only works in MATLAB, not in TIO/Octave) – Sanchises – 2017-11-15T09:19:18.583

6

Husk, 3 bytes

ḋtḋ

Try it online!

Explanation:

    -- implicit input, e.g. 350
  ḋ -- convert number to list of binary digits (TNum -> [TNum]): [1,0,1,0,1,1,1,1,0]
 t  -- remove first element: [0,1,0,1,1,1,1,0]
ḋ   -- convert list of binary digits to number ([TNum] -> TNum): 94

Laikoni

Posted 2017-11-14T18:59:57.710

Reputation: 23 676

Similarly to the Jelly solution, this seems like it's actually 5 bytes, not 3. – Bartek Banachewicz – 2017-11-15T12:31:39.277

1@BartekBanachewicz Similarly to Jelly, Husk uses its own codepage, so this is actually 3 bytes :P – HyperNeutrino – 2017-11-15T13:00:42.150

@BartekBanachewicz See here for the codepage: https://github.com/barbuz/Husk/wiki/Codepage

– Laikoni – 2017-11-15T13:08:53.017

6

Java (OpenJDK 8), 23 bytes

n->n^n.highestOneBit(n)

Try it online!

Sorry, built-in :-/

Olivier Grégoire

Posted 2017-11-14T18:59:57.710

Reputation: 10 647

Java with a build-in that some other popular languages like .NET and Python has not?! o.Ô +1 to that. Was about to post something longer without build-ins.. Yours is 15 bytes shorter. XD – Kevin Cruijssen – 2017-11-15T11:14:29.930

@KevinCruijssen Something like n->n^1<<(int)Math.log2(n) will work and is likely shorter than 38 bytes. It was my second (yet untested) idea, if the highestOneBit one didn't work appropriately. Out of curiosity, what was your solution – Olivier Grégoire – 2017-11-15T20:54:26.020

Mine was n->n^1<<(int)(Math.log(n)/Math.log(2)) because Math.log2 doesn't exist in Java. ;P Only Math.log, Math.log10 and Math.loglp are available. – Kevin Cruijssen – 2017-11-16T07:57:13.560

2

I was going to post the same, only minus instead of xor. Remembered the method from this

– JollyJoker – 2017-11-16T08:26:26.530

1@KevinCruijssen Oops, Math.log2 doesn't exist indeed... My bad. See? One nice method (highestOneBit) exists but not another one (Math.log2). Java is weird ;-) – Olivier Grégoire – 2017-11-16T08:41:36.093

5

Python 3, 30 bytes

-8 bytes thanks to caird coinheringaahing. I typed that from memory. :o

lambda n:int('0'+bin(n)[3:],2)

Try it online!

totallyhuman

Posted 2017-11-14T18:59:57.710

Reputation: 15 378

Why not lambda n:int(bin(n)[3:],2)?

– caird coinheringaahing – 2017-11-14T21:02:41.513

Well, a) that would error on 1, b) I'm dumb enough to not think of that. But I did fix it with a minor change. Thanks! – totallyhuman – 2017-11-14T21:06:04.140

I've edited the code so that it works, (and saves 4 bytes) – caird coinheringaahing – 2017-11-14T21:07:26.853

That still errors on 1. – totallyhuman – 2017-11-14T21:08:04.103

@cairdcoinheringaahing That was my original answer, but then I realised it errored on 1. The workaround ends up longer than a simple XOR method

– FlipTack – 2017-11-14T21:52:25.583

5

Python 2, 27 bytes

lambda n:n-2**len(bin(n))/8

Try it online!

Explanation

lambda n:n-2**len(bin(n))/8  # Lambda Function: takes `n` as an argument
lambda n:                    # Declaration of Lambda Function
              len(bin(n))    # Number of bits + 2
           2**               # 2 ** this ^
                         /8  # Divide by 8 because of the extra characters in the binary representation
         n-                  # Subtract this from the original

HyperNeutrino

Posted 2017-11-14T18:59:57.710

Reputation: 26 575

...Just when I was working the bitwise math out. :P – totallyhuman – 2017-11-14T19:05:09.143

@totallyhuman heh sorry but beat you to it :P – HyperNeutrino – 2017-11-14T19:05:42.377

2**len(bin(n))/8 can also be spelled 1<<len(bin(n))-3, and then it will work in both 2 and 3 (no bytes saved/added). – Mego – 2017-11-14T19:08:23.923

@Mego Cool, thanks for the addition! – HyperNeutrino – 2017-11-14T19:08:51.040

5

Ohm v2, 3 bytes

b(ó

Try it online!

Cinaski

Posted 2017-11-14T18:59:57.710

Reputation: 1 588

4

Mathematica, 37 bytes

Rest[#~IntegerDigits~2]~FromDigits~2&

Try it online!

J42161217

Posted 2017-11-14T18:59:57.710

Reputation: 15 931

4

JavaScript, 22 20 bytes

Saved 2 bytes thanks to ovs

a=>a^1<<Math.log2(a)

Try it online!

Another approach, 32 bytes

a=>'0b'+a.toString`2`.slice`1`^0

Try it online!

user72349

Posted 2017-11-14T18:59:57.710

Reputation:

why would you do .slice`1`^0 when .slice(1)^0 would work just as well, haha – ETHproductions – 2017-11-15T00:19:55.427

@ETHproductions. This one looks better :) – None – 2017-11-15T07:54:47.150

4

J, 6 bytes

}.&.#:

Pretty simple.

Explanation

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead

cole

Posted 2017-11-14T18:59:57.710

Reputation: 3 526

I was going to post this :( – Cyoce – 2017-11-15T06:07:26.550

@Cyoce Me too... – Adám – 2017-11-15T09:52:50.750

4

APL (Dyalog), 10 bytes

Tacit prefix function.

2⊥1↓2∘⊥⍣¯1

Try it online!

2∘⊥… decode from base-2…
 …⍣¯1 negative one time (i.e. encode in base-2)

1↓ drop the first bit

2⊥ decode from base-2

Adám

Posted 2017-11-14T18:59:57.710

Reputation: 37 779

4

Ruby, 26 bytes

-7 Bytes thanks to Ventero. -2 Bytes thanks to historicrat.

->n{/./=~'%b'%n;$'.to_i 2}

displayname

Posted 2017-11-14T18:59:57.710

Reputation: 151

You can save a few bytes by just skipping the first character and dropping redundant parentheses: ->n{n.to_s(2)[1..-1].to_i 2} – Ventero – 2017-11-14T21:37:42.457

->n{/./=~'%b'%n;$'.to_i 2} – histocrat – 2017-11-14T23:11:07.003

4

C (gcc), 38 bytes

Built-in in gcc used.

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

Colera Su

Posted 2017-11-14T18:59:57.710

Reputation: 2 291

Replacing 31- with ~ should save two bytes. – None – 2017-11-15T18:36:35.053

@ThePirateBay it depends on hardware whether the shift is masked. On my computer, it will output 0. – Colera Su – 2017-11-16T14:35:41.983

4

ARM Assembly, 46 43 bytes

(You can omit destination register on add when same as source)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret

Michael Dorgan

Posted 2017-11-14T18:59:57.710

Reputation: 221

What flavour of ARM assembly syntax is this? My GNU assembler doesn't understand shr/shl/ret and wants instead something like lsr/lsl/bx lr. – Ruslan – 2017-11-16T20:19:01.110

Probably mixing syntax across multiple versions (ret is from aarch64), though I thought that the assembler would pseudo op these for you. For purposes of here, though, using the older and direct lsl/lsr is probably correct. – Michael Dorgan – 2017-11-17T17:44:04.780

Funny thing, i can do it in 1 less operation, but I the byte size goes up by 2. Ah code golf. – Michael Dorgan – 2017-11-20T18:43:28.567

3

APL (Dyalog Unicode), 9 bytes

⊢-2*∘⌊2⍟⊢

Try it online!

-1 byte thanks to Adam

HyperNeutrino

Posted 2017-11-14T18:59:57.710

Reputation: 26 575

Completely correct, although I would have used TIO to generate a template for me. Anyway, ⊢-2*∘⌊2⍟⊢ saves a byte.

– Adám – 2017-11-14T19:37:20.607

I was sad that APL wasn't represented, and there is was, almost lost in the scroll! I miss APL. – cmm – 2017-11-15T00:47:25.093

@cmm APL is alive and well. Feel free to hang out in the Stack Exchange APL chat room.

– Adám – 2017-11-15T09:46:19.703

3

Pyth, 5 bytes

a^2sl

Test suite.

Explanation:

    l   Log base 2 of input.
   s    Cast ^ to integer (this is the position of the most significant bit.)
 ^2     Raise 2 to ^ (get the value of said bit)
a       Subtract ^ from input

Steven H.

Posted 2017-11-14T18:59:57.710

Reputation: 2 841

3

Alice, 8 bytes

./-l
o@i

Try it online!

Explanation

.   Duplicate an implicit zero at the bottom of the stack. Does nothing.
/   Switch to Ordinal mode, move SE.
i   Read all input as a string.
l   Convert to lower case (does nothing, because the input doesn't contain letters).
i   Try reading all input again, pushes an empty string.
/   Switch to Cardinal mode, move W.
.   Duplicate. Since we're in Cardinal mode, this tries to duplicate an integer.
    To get an integer, the empty string is discarded implicitly and the input is 
    converted to the integer value it represents. Therefore, at the end of this,
    we get two copies of the integer value that was input.
l   Clear lower bits. This sets all bits except the MSB to zero.
-   Subtract. By subtracting the MSB from the input, we set it to zero. We could
    also use XOR here.
/   Switch to Ordinal, move NW (and immediately reflect to SW).
o   Implicitly convert the result to a string and print it.
/   Switch to Ordinal, move S.
@   Terminate the program.

Martin Ender

Posted 2017-11-14T18:59:57.710

Reputation: 184 808

3

Japt, 6 bytes

^2p¢ÊÉ

Try it online!

Explanation

^2p¢ÊÉ
   ¢     Get binary form of input
    Ê    Get length of that
     É   Subtract 1
 2p      Raise 2 to the power of that
^        XOR with the input

If input 1 can fail: 4 bytes

¢Ån2

Try it online!

Explanation: get input binary (¢), slice off first char (Å), parse as binary back to a number (n2).

Justin Mariner

Posted 2017-11-14T18:59:57.710

Reputation: 4 746

3

Octave, 20 bytes

@(x)x-2^fix(log2(x))

Try it online!

Luis Mendo

Posted 2017-11-14T18:59:57.710

Reputation: 87 464

3

PARI/GP, 18 bytes

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

Alternate solution:

n->n-2^exponent(n)

Charles

Posted 2017-11-14T18:59:57.710

Reputation: 2 435

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?

– Jeppe Stig Nielsen – 2017-11-15T11:03:31.200

@JeppeStigNielsen Oops, fixed -- that's what I get for submitting from my phone. Yes, the second one is a new function. – Charles – 2017-11-15T16:36:59.770

@JeppeStigNielsen I just checked, exponent was added 5 days ago, compared to this challenge which was added yesterday. :) – Charles – 2017-11-15T16:38:08.083

3

CJam, 7 bytes

{2b()b}

Try it online!

Explanation:

{     }  Block:         267
 2b      Binary:        [1 0 0 0 0 1 0 1 1]
   (     Pop:           [0 0 0 0 1 0 1 1] 1
    )    Increment:     [0 0 0 0 1 0 1 1] 2
     b   Base convert:  11

Reuse the MSB (which is always 1) to avoid having to delete it; the equivalent without that trick would be {2b1>2b} or {2b(;2b}.

Esolanging Fruit

Posted 2017-11-14T18:59:57.710

Reputation: 13 542

3

Retina, 15 13 bytes

^(^1|\1\1)*1

Try it online!

Input and output in unary (the test suite includes conversion from and to decimal for convenience).

Explanation

This is quite easy to do in unary. All we want to do is delete the largest power of 2 from the input. We can match a power of 2 with some forward references. It's actually easier to match values of the form 2n-1, so we'll do that and match one 1 separately:

^(^1|\1\1)*1

The group 1 either matches a single 1 at the beginning to kick things off, or it matches twice what it did on the last iteration. So it matches 1, then 2, then 4 and so on. Since these get added up, we're always one short of a power of 2, which we fix with the 1 at the end.

Due the trailing linefeed, the match is simply removed from the input.

Martin Ender

Posted 2017-11-14T18:59:57.710

Reputation: 184 808

3

Excel, 36 31 bytes

-5 bytes thanks to @IanM_Matrix1

=BIN2DEC(MID(DEC2BIN(A1),2,99))

Nothing interesting.

Wernisch

Posted 2017-11-14T18:59:57.710

Reputation: 2 534

Reduce the size to 31 bytes by replacing REPLACE with a MID: =BIN2DEC(MID(DEC2BIN(A1),2,99)) – IanM_Matrix1 – 2017-11-16T16:40:35.073

3

R, 28 bytes

function(x)x-2^(log2(x)%/%1)

Try it online!

Easiest to calculate the most significant bit via 2 ^ floor(log2(x)) rather than carry out base conversions, which are quite verbose in R

user2390246

Posted 2017-11-14T18:59:57.710

Reputation: 1 391

3

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!

user28667

Posted 2017-11-14T18:59:57.710

Reputation: 579

1

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!

– Laikoni – 2017-11-16T14:42:14.697

3

Excel, 20 bytes

=A1-2^INT(LOG(A1,2))

IanM_Matrix1

Posted 2017-11-14T18:59:57.710

Reputation: 131

Welcome to the site! :) – James – 2017-11-16T16:48:59.920

3

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.

peter ferrie

Posted 2017-11-14T18:59:57.710

Reputation: 804

2

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.

NieDzejkob

Posted 2017-11-14T18:59:57.710

Reputation: 4 630

The () is apparently unnecessary – HyperNeutrino – 2017-11-14T19:16:07.360

17 bytes – HyperNeutrino – 2017-11-14T19:16:23.263

117 bytes: #-2^⌊Log2@#⌋& – J42161217 – 2017-11-14T19:33:15.793

@Jenny_mathy Someone came up with the same exact program? I didn't know this was a sequence in OEIS – NieDzejkob – 2017-11-14T19:58:28.843

1Too bad we can't do #~BitClear~-1& which would be 14 bytes. Seems like the natural extension of the syntax. Maybe in version 12. – Kelly Lowder – 2017-11-14T20:07:55.010

@KellyLowder Could you explain that syntax? – NieDzejkob – 2017-11-14T20:20:38.420

@NieDzejkob, Assuming you're OK with the infix notation, the idea would be that the -1 rolls around to the other side of the list of bits (the most significant side), like Part[x,-1] takes from the right of the list while Part[x,1] takes from the left. Many other functions use this convention such as Take, Drop, Span. Since BitClear only accepts integers this would cause no problems. – Kelly Lowder – 2017-11-14T20:31:11.003

@KellyLowder no, I see how negative numbers should wrap around. I don't see how this makes Mathematica do BitClear[#,-1] – NieDzejkob – 2017-11-14T20:32:40.483

@NieDzejkob, well do you agree that BitClear[#,BitLength@#-1]& gives the correct answer? I'm saying the syntax should allow the BitLength@# to be omitted. – Kelly Lowder – 2017-11-14T20:37:33.460

Let us continue this discussion in chat.

– NieDzejkob – 2017-11-14T21:06:30.243

2

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.

histocrat

Posted 2017-11-14T18:59:57.710

Reputation: 20 600

2

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.

James Holderness

Posted 2017-11-14T18:59:57.710

Reputation: 8 298

2

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)

steenbergh

Posted 2017-11-14T18:59:57.710

Reputation: 7 772

2

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.

idrougge

Posted 2017-11-14T18:59:57.710

Reputation: 641

an explanation would be nice – Titus – 2017-11-16T11:52:12.707

Consider it done. – idrougge – 2017-11-17T16:48:28.300

2

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.

CSM

Posted 2017-11-14T18:59:57.710

Reputation: 219

2

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.

Alex Robinson

Posted 2017-11-14T18:59:57.710

Reputation: 121

1Often assembly submissions are rated in the size of their assembled machine code output (which usually results in a way better score ;-) ) – Matteo Italia – 2017-11-17T14:31:41.077

@MatteoItalia that's something I'm going to look into then! – Alex Robinson – 2017-11-17T15:46:50.277

2

Julia, 24 bytes

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

Try it online!

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

LukeS

Posted 2017-11-14T18:59:57.710

Reputation: 421

2Welcome to PPCG! :) – Laikoni – 2017-12-17T15:11:32.590

1

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.

AdmBorkBork

Posted 2017-11-14T18:59:57.710

Reputation: 41 581

You can get down to 48 bytes actually: $m=[math];$_-$m::pow(2,$m::floor($m::log($_,2))) – cogumel0 – 2017-11-29T11:30:31.853

@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! – AdmBorkBork – 2017-11-29T13:19:16.373

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 ;) – cogumel0 – 2017-11-29T13:37:28.390

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]) – cogumel0 – 2017-11-29T13:43:51.417

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. – AdmBorkBork – 2017-11-29T13:57:38.083

1

Pyth, 6 bytes

it.BQ2

Try it online!

HyperNeutrino

Posted 2017-11-14T18:59:57.710

Reputation: 26 575

-1 bytes – Steven H. – 2017-11-14T19:25:44.417

1

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.

Ayb4btu

Posted 2017-11-14T18:59:57.710

Reputation: 541

Well, there's a better way

– NieDzejkob – 2017-11-14T19:49:02.583

“unfortunately” … err. – Konrad Rudolph – 2017-11-15T09:51:11.953

@KonradRudolph "unfortunately" in the sense that it stops me having a shorter answer :-P. Probably "fortunate" in every other use. – Ayb4btu – 2017-11-15T21:37:01.697

In the mathematical approach you can directly write System.Math.Log... and remove the using-Statement. – raznagul – 2017-11-17T11:39:26.400

1

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.

Stewie Griffin

Posted 2017-11-14T18:59:57.710

Reputation: 43 471

1

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.

Sean

Posted 2017-11-14T18:59:57.710

Reputation: 4 136

1

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!

Mr. Xcoder

Posted 2017-11-14T18:59:57.710

Reputation: 39 774

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

– Justin Mariner – 2017-11-14T20:52:29.973

1

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]

caird coinheringaahing

Posted 2017-11-14T18:59:57.710

Reputation: 13 702

1

CJam - 8 bytes

ri2b(;2b

Explanation

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

FedeWar

Posted 2017-11-14T18:59:57.710

Reputation: 271

1You can replace (;2 with (). – Martin Ender – 2017-11-15T08:40:59.937

@MartinEnder Thanks, great idea – FedeWar – 2017-11-15T09:56:48.023

1

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.

Shaggy

Posted 2017-11-14T18:59:57.710

Reputation: 24 623

1

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.

Nitrodon

Posted 2017-11-14T18:59:57.710

Reputation: 9 181

1

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

Neil

Posted 2017-11-14T18:59:57.710

Reputation: 95 035

1

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!

ATaco

Posted 2017-11-14T18:59:57.710

Reputation: 7 898

1

Ruby, 22 bytes

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

Try it online!

Reinstate Monica -- notmaynard

Posted 2017-11-14T18:59:57.710

Reputation: 1 053

1

Bash, 27 bytes

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

Try it online!

Unihedron

Posted 2017-11-14T18:59:57.710

Reputation: 1 115

1

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;

anatolyg

Posted 2017-11-14T18:59:57.710

Reputation: 10 719

1

PHP, 28 25+1 bytes

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

Run as pipe with -nF or try it online.

Titus

Posted 2017-11-14T18:59:57.710

Reputation: 13 814

1-4 bytes by replacing &~ with ^. – Colera Su – 2017-11-16T23:36:11.110

1@ColeraSu -3 bytes. +1 is for -F. But thanks. – Titus – 2017-11-16T23:44:36.207

1

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

PrincePolka

Posted 2017-11-14T18:59:57.710

Reputation: 653

1

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!

Samsquanch

Posted 2017-11-14T18:59:57.710

Reputation: 271

1

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!

jq170727

Posted 2017-11-14T18:59:57.710

Reputation: 411

1

Common Lisp, 40 bytes

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

Try it online!

Renzo

Posted 2017-11-14T18:59:57.710

Reputation: 2 260

1

Python, 32 bytes

lambda n:n-2**(n.bit_length()-1)

ShpielMeister

Posted 2017-11-14T18:59:57.710

Reputation: 111

3Hello, 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). – James – 2017-12-11T22:01:00.540

Also, you could remove the spaces around the minus sign: n-2**(n.bit_length()-1) to save 2 bytes. – James – 2017-12-11T22:01:36.050

1@DJMcMayhem thanks for the courteous pointers. appreciate the gentle schooling – ShpielMeister – 2017-12-11T22:02:27.550

1

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

Giuseppe

Posted 2017-11-14T18:59:57.710

Reputation: 21 077

1

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.

xnor

Posted 2017-11-14T18:59:57.710

Reputation: 115 687

1

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

DLosc

Posted 2017-11-14T18:59:57.710

Reputation: 21 213

0

Actually, 7 bytes

;╘L2ⁿ@-

Try it online!

HyperNeutrino

Posted 2017-11-14T18:59:57.710

Reputation: 26 575

0

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

Riley

Posted 2017-11-14T18:59:57.710

Reputation: 11 345

The logarithm version is a bit shorter, too bad we need to handle 1 though :(, otherwise the 3-byter would be the shortest – Mr. Xcoder – 2017-11-14T20:04:27.510

@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 – NieDzejkob – 2017-11-14T20:22:49.270

@NieDzejkob The answer I linked to is my own answer and does use logarithms. – Mr. Xcoder – 2017-11-14T20:24:05.550

@Mr.Xcoder then the StackExchange app is utterly broken, let me see – NieDzejkob – 2017-11-14T20:25:04.097

0

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

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

Try it online!

Xcali

Posted 2017-11-14T18:59:57.710

Reputation: 7 671

0

GolfScript - 13 bytes

~2base(;2base

Explanation

~      # Parse argument
2base  # Convertion to base 2
(;     # Cut away first byte
2base  # Convertion from base 2

FedeWar

Posted 2017-11-14T18:59:57.710

Reputation: 271

0

Tcl, 45 bytes

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

Try it online!

sergiol

Posted 2017-11-14T18:59:57.710

Reputation: 3 055

0

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.

ETHproductions

Posted 2017-11-14T18:59:57.710

Reputation: 47 880

0

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.

anatolyg

Posted 2017-11-14T18:59:57.710

Reputation: 10 719

0

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

Ruslan

Posted 2017-11-14T18:59:57.710

Reputation: 1 283

0

C++, 42 bytes

int f(int n){return n-exp2((int)log2(n));}

uKER

Posted 2017-11-14T18:59:57.710

Reputation: 9

2Could 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 – James – 2017-11-16T21:20:00.823

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. – uKER – 2017-11-16T21:26:18.740

1

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.

– James – 2017-11-16T21:28:43.693

I see. No problem then. – uKER – 2017-11-16T21:31:28.220

1In 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));} – CSM – 2017-11-18T14:37:49.257

0

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

Tornado547

Posted 2017-11-14T18:59:57.710

Reputation: 389

0

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

Bolce Bussiere

Posted 2017-11-14T18:59:57.710

Reputation: 970

0

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;

l4m2

Posted 2017-11-14T18:59:57.710

Reputation: 5 985