title: How even is a number?

text:
# Question
Title: How even is a number?
The ancient Greeks had these things called singly and doubly even numbers. An example of a singly even number is 14. It can be divided by 2 once, and has at that point become an odd number (7), after which it is not divisible by 2 anymore. A doubly even number is 20. It can be divided by 2 twice, and then becomes 5.

Your task is to write a function or program that takes an integer as input, and outputs the number of times it is divisible by 2 as an integer, in as few bytes as possible. The input will be a nonzero integer (any positive or negative value, within the limits of your language).

Test cases:

```
14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

```

The answer with the least bytes wins.

**Tip:** Try converting the number to base 2. See what that tells you.

# Answer
> 10 votes
# Jelly, 2 bytes

```
ọ2

```

Try it online!

## How it works

```
ọ2 - Main link. Takes n on the left
ọ  - How many times is n divisible by...
 2 - ...2?

```

# Answer
> 97 votes
# x86\_64 machine code, 4 bytes

The BSF (bit scan forward) instruction does exactly this!

```
0x0f    0xbc    0xc7    0xc3

```

In gcc-style assembly, this is:

```
    .globl  f
f:
    bsfl    %edi, %eax
    ret

```

The input is given in the EDI register and returned in the EAX register as per standard 64-bit calling conventions.

Because of two's complement binary encoding, this works for -ve as well as +ve numbers.

Also, despite the documentation saying *"If the content of the source operand is 0, the content of the destination operand is undefined."*, I find on my Ubuntu VM that the output of `f(0)` is 0.

### Instructions:

* Save the above as `evenness.s` and assemble with `gcc -c evenness.s -o evenness.o`
* Save the following test driver as `evenness-main.c` and compile with `gcc -c evenness-main.c -o evenness-main.o`:

```
#include <stdio.h>

extern int f(int n);

int main (int argc, char **argv) {
    int i;

    int testcases[] = { 14, 20, 94208, 7, 0, -4 };

    for (i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++) {
        printf("%d, %d\n", testcases[i], f(testcases[i]));
    }

    return 0;
}

```

Then:

* Link: `gcc evenness-main.o evenness.o -o evenness`
* Run: `./evenness`

---

@FarazMasroor asked for more details on how this answer was derived.

I am more familiar with than the intricacies of x86 assembly, so typically I use a compiler to generate assembly code for me. I know from experience that gcc extensions such as `__builtin_ffs()`, `__builtin_ctz()` and `__builtin_popcount()` typically compile and assemble to 1 or 2 instructions on x86. So I started out with a function like:

```
int f(int n) {
    return __builtin_ctz(n);
}

```

Instead of using regular gcc compilation all the way to object code, you can use the `-S` option to compile just to assembly - `gcc -S -c evenness.c`. This gives an assembly file `evenness.s` like this:

```
    .file   "evenness.c"
    .text
    .globl  f
    .type   f, @function
f:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    rep bsfl    %eax, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   f, .-f
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

```

A lot of this can be golfed out. In particular we know that the calling convention for functions with `int f(int n);` signature is nice and simple - the input param is passed in the `EDI` register and the return value is returned in the `EAX` register. So we can take most of instructions out - a lot of them are concerned with saving registers and setting up a new stack frame. We don't use the stack here and only use the `EAX` register, so don't need to worry about other registers. This leaves "golfed" assembly code:

```
    .globl  f
f:
    bsfl    %edi, %eax
    ret

```

Note as @zwol points out, you can also use optimized compilation to achieve a similar result. In particular `-Os` produces exactly the above instructions (with a few additional assembler directives that don't produce any extra object code.)

This is now assembled with `gcc -c evenness.s -o evenness.o`, which can then be linked into a test driver program as described above.

There are several ways to determine the machine code corresponding to this assembly. My favourite is to use the gdb `disass` disassembly command:

```
$ gdb ./evenness
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
...
Reading symbols from ./evenness...(no debugging symbols found)...done.
(gdb) disass /r f
Dump of assembler code for function f:
   0x00000000004005ae <+0>: 0f bc c7    bsf    %edi,%eax
   0x00000000004005b1 <+3>: c3  retq
   0x00000000004005b2 <+4>: 66 2e 0f 1f 84 00 00 00 00 00   nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005bc <+14>:    0f 1f 40 00 nopl   0x0(%rax)
End of assembler dump.
(gdb)

```

So we can see that the machine code for the `bsf` instruction is `0f bc c7` and for `ret` is `c3`.

# Answer
> 31 votes
# Python, 25 bytes

```
lambda n:len(bin(n&-n))-3

```

`n & -n` zeroes anything except the least significant bit, e.g. this:

```
100010101010100000101010000
            v
000000000000000000000010000

```

We are interested in the number of trailing zeroes, so we convert it to a binary string using `bin`, which for the above number will be `"0b10000"`. Since we don't care about the `0b`, nor the `1`, we subtract 3 from that strings length.

# Answer
> 22 votes
# Jelly, 4 bytes

```
Æfċ2

```

In the latest version of Jelly, `ÆEḢ` (3 bytes) works.

```
Æf      Calculate the prime factorization. On negative input, -1 appended to the end.
  ċ2    Count the 2s.

```

Try it here.

# Answer
> 21 votes
# Pyth, 6 bytes

```
/P.aQ2

```

Try it here.

```
 P.aQ         In the prime factorization of the absolute value of the input
/    2        count the number of 2s.

```

# Answer
> 16 votes
# JavaScript (ES6), 18 bytes

```
n=>Math.log2(n&-n)

```

4 bytes shorter than `31-Math.clz32`. Hah.

# Answer
> 15 votes
# JavaScript ES6, ~~22~~ 19 bytes

```
f=x=>x%2?0:f(x/2)+1

```

Looks like recursion is the shortest route.

# Answer
> 7 votes
# MATL, 5 bytes

```
Yf2=s

```

This works for all integers.

**Try it online!**

```
Yf      % implicit input. Compute (repeated) prime factors. For negative input
        % it computes the prime factors of the absolute value, except that for
        % -1 it produces an empty array instead of a single 1
2=s     % count occurrences of "2" in the array of prime factors

```

# Answer
> 6 votes
## Pyth, 8 bytes

```
lec.BQ\1

```

```
     Q    autoinitialized to eval(input())
   .B     convert to binary string
  c   \1  split on "1", returning an array of runs of 0s
 e        get the last run of 0s, or empty string if number ends with 1
l         take the length

```

For example, the binary representation of `94208` is:

```
10111000000000000

```

After splitting on `1`s and taking the last element of the resulting array, this becomes:

```
000000000000

```

That's 12 zeroes, so it's "12-ly even."

This works because `x / 2` is essentially `x >> 1`—that is, a bitshift right of `1`. Therefore, a number is divisible by 2 only when the LSB is `0` (just like how a decimal number is divisible by 10 when its last digit is `0`).

# Answer
> 6 votes
# 05AB1E, ~~4~~ 5 bytes

Now supports negative numbers. Code:

```
Äb1¡g

```

Try it online!

Explanation:

```
Ä      # Abs(input)
 b     # Convert the number to binary
  1¡   # Split on 1's
    g  # Take the length of the last element

```

Uses CP-1252 encoding.

# Answer
> 6 votes
## C, 36 (28) bytes

```
int f(int n){return n&1?0:f(n/2)+1;}

```

(Not testing for zero argument as a nonzero argument was specified.)

**Update (in response to comment)**: If we allow K&R style function declarations, then we can have a 28-byte version:

```
f(n){return n&1?0:f(n/2)+1;}

```

In this case, we rely on the fact that the compiler defaults both `n` and the return type of `f` to `int`. This form generates a warning with C99 though and does not compile as valid C++ code.

# Answer
> 6 votes
## Pyth, 6 bytes

```
x_.BQ1

```

Basically just

```
convert2BinString(evaluatedInput())[::-1].index("1")

```

# Answer
> 5 votes
## Java 7, 39 or maybe 44 bytes

```
int s(int a){return a%2!=0?0:s(a/2)+1;}

int s(int a){return a%2!=0|a==0?0:s(a/2)+1;}

```

Yay recursion! I had to use a `!=` instead of a shorter comparison so it wouldn't overflow on negative input, but other than that it's pretty straightforward. If it's odd, send a zero. If even, add one and do it again.

There are two versions because right now output for zero is unknown. The first will recurse until the stack overflows, and output nothing, because 0 is infinitely even. The second spits out a nice, safe, but probably-not-mathematically-rigorous 0 for output.

# Answer
> 5 votes
# Ruby 24 bytes

My first code golf submission (yey!)

```
("%b"%$*[0])[/0*$/].size

```

**How I got here**:

First I wanted to get code that actually fulfilled the spec to get my head around the problem, so I built the method without regards to number of bytes:

```
def how_even(x, times=1)
  half = x / 2
  if half.even?
    how_even(half, times+1)
  else
    times
  end
end

```

with this knowledge I de-recursed the function into a while loop and added `$*` (ARGV) as the input and i as the count of how many times the number has been halved before it becomes odd.

```
x=$*[0];i=1;while(x=x/2)%2<1;i+=1;end;i

```

I was quite proud of this and almost submitted it before it struck me that all this dividing by two sounded a bit binary to me, being a software engineer but not so much a computer scientist this wasn't the first thing that sprung to mind.

So I gathered some results about what the input values looked like in binary:

```
input      in binary      result
---------------------------------
   14               1110   1
   20              10100   2
94208  10111000000000000  12

```

I noticed that the result was the number of positions to the left we have to traverse before the number becomes odd.

Doing some simple string manipulations I split the string on the last occurrence of 1 and counted the length of remaining 0s:

```
("%b"%$*[0])[/0*$/].size

```

using `("%b" % x)` formatting to turn a number to binary, and String#slice to slice up my string.

I have learnt a few things about ruby on this quest and look forward to more golfs soon!

# Answer
> 4 votes
# C, 37 bytes

`f(int x){return x?x&1?0:1+f(x/2):0;}` Recursively check the last bit until it's not a 0.

# Answer
> 4 votes
# JavaScript (ES6), 20 bytes 19 bytes.

```
f=x=>~x%2&&1+f(x/2)

```

This is a port of the Haskell solution by @nimi to JavaScript. It uses the "short-circuit" properties of `&&` which returns its left side if it is falsey (which in this case is `-0`) or else returns its right side. To implement `odd x = 0` we therefore make the left hand side `1 - (x % 2)` which bubbles `0` through the `&&`, otherwise we recurse to `1 + f(x / 2)`.

The shaving of `1 - (x % 2)` as `(~x) % 2` is due to @Neil below, and has the strange property that causes the above function to emit `-0` for small odd numbers. This value is a peculiarity of JS's decision that integers are IEEE754 doubles; this system has a separate `+0` and `-0` which are special-cased in JavaScript to be `===` to each other. The `~` operator computes the 32-bit-signed-integer bitwise inversion for the number, which for small odd numbers will be a negative even number. (The positive number `Math.pow(2, 31) + 1` for example produces `0` rather than `-0`.) The strange restriction to the 32-bit-signed integers does not have any other effects; in particular it does not affect correctness.

# Answer
> 4 votes
# Perl 6, ~~23~~ 18 bytes

```
{+($_,*/2...^*%2)}

```

**usage**

```
> my &f = {+($_,*/2...^*%2)}
-> ;; $_? is raw { #`(Block|117104200) ... }
> f(14)
1
> f(20)
2
> f(94208)
12
> f(7)
0
> f(-4)
2

```

# Answer
> 4 votes
# J, 6 bytes

```
1&q:@|

```

Explanation:

```
     |    absolute value
1&q:      exponent of 2 in the prime factorization

```

# Answer
> 4 votes
# APL (Dyalog Unicode), 10 bytes

My 100th answer.

```
⊥⍨∘~2∘⊥⍣¯1

```

Try it online!

Explanation:

```
⊥⍨∘~2∘⊥⍣¯1
    2∘⊥⍣¯1   ⍝ convert the number to binary.
   ~         ⍝ negate it
⊥⍨           ⍝ count trailing ones in the negated number,
             ⍝ effectively counting trailing zeros in the number,
             ⍝ effectively counting how many times is the number divisible by 2.

```

# Answer
> 4 votes
# Java, 27 bytes

```
Long::numberOfTrailingZeros

```

Try it online!

## Explanation

The number of times a number can be divided by 2 is equal the number of 0s after the rightmost 1 in its binary representation; Java has a built-in method for finding this. Using `Long` instead of `Integer` saves 3 bytes.

See also: `Long.numberOfTrailingZeros` documentation

# Answer
> 4 votes
# Vyxal, 2 bytes

Try it Online!

This one by @lyxal

```
2Ǒ # I'm running out of things to say for this comment line
 Ǒ # How many times is the input divisible by...
2  # 2

```

# Vyxal, 4 bytes

```
Eġ∆l

```

Try it Online!

Ported from the Desmos answer.

```
Eġ∆l # 4 bytes!
E    # 2^input
 ġ   # GCD of that and the input
  ∆l # log2

```

# Vyxal, 5 bytes

```
bṘȧ1ḟ

```

Try it Online!

Strategy from the osabie answer. Suprised that there has been no Vyxal answer for a such a popular question. Bit twiddling also gives 5 bytes.

```
bṘȧ1ḟ # This comment line needs some love
b     # Convert to binary
 Ṙ    # Reverse
  ȧ   # Absolute value of each element in the list. This is to handle negative numbers correctly
   1ḟ # First index of 1

```

# Answer
> 4 votes
# Rust, 18 bytes

```
i8::trailing_zeros

```

Attempt This Online!

It's a builtin :) Replace `i8` with any other integer type and it will also work.

# Answer
> 3 votes
# Retina, ~~29~~ 17

```
+`\b(1+)\1$
;$1
;

```

Try it online!

2 bytes saved thanks to Martin!

Takes unary input. This repeatedly matches the largest amount of `1`s it can such that that number of `1`s matches exactly the rest of the `1`s in the number. Each time it does this it prepends a `;` to the string. At the end, we count the number of `;`s in the string.

If you want decimal input, add:

```
\d+
$0$*1

```

to the beginning of the program.

# Answer
> 3 votes
# Brachylog, ~~27~~ 15 bytes

```
$pA:2xlL,Al-L=.

```

### Explanation

```
$pA             § Unify A with the list of prime factors of the input
   :2x          § Remove all occurences of 2 in A
      lL,       § L is the length of A minus all the 2s
         Al-L=. § Unify the output with the length of A minus L

```

# Answer
> 3 votes
## Haskell, 28 bytes

```
f x|odd x=0|1<2=1+f(div x 2)

```

Usage example: `f 94208`-\> `12`.

If the number is odd, the result is `0`, else `1` plus a recursive call with half the number.

# Answer
> 3 votes
# Befunge, 20

```
&:2%#|_\1+\2/#
   @.<

```

Code execution keeps moving to the right and wrapping around to the second character of the first line (thanks to the trailing `#`) until `2%` outputs `1`, which causes `_` to switch the direction to left, then `|` to up, which wraps around to the `<` on the second row, which outputs and exits. We increment the second-to-the-top element of the stack every time through the loop, then divide the top by 2.

# Answer
> 3 votes
# Jolf, 6 bytes

Try it here!

```
Zlm)j2
Zl   2  count the number occurrences of 2 in
  m)j   the prime factorization of j (input)

```

Rather simple... Kudos to ETHProductions for ousting Jolf with the version that really should work!

# Answer
> 3 votes
## ES6, 22 bytes

```
n=>31-Math.clz32(n&-n)

```

Returns -1 if you pass 0.

# Answer
> 3 votes
# PARI/GP, 17 bytes

```
n->valuation(n,2)

```

# Answer
> 3 votes
## 6502 machine language, 7 bytes

To find the place value of the least significant 1 bit of the nonzero value in the accumulator, leaving the result in register X:

```
A2 FF E8 4A 90 FC 60

```

To run this on the 6502 simulator on e-tradition.net, prefix it with `A9` followed by an 8-bit integer.

This disassembles to the following:

```
count_trailing_zeroes:
    ldx #$FF
loop:
    inx
    lsr a     ; set carry to 0 iff A divisible by 2, then divide by 2 rounding down
    bcc loop  ; keep looping if A was divisible by 2
    rts       ; return with result in X

```

This is equivalent to the following C, except that C requires `int` to be at least 16-bit:

```
unsigned int count_trailing_zeroes(int signed_a) {
    unsigned int carry;
    unsigned int a = signed_a;  // cast to unsigned makes shift well-defined
    unsigned int x = UINT_MAX;
    do {
        x += 1;
        carry = a & 1;
        a >>= 1;
    } while (carry == 0);
    return x;
}

```

The same works on a 65816, assuming MX = 01 (16-bit accumulator, 8-bit index), and is equivalent to the above C snippet.

# Answer
> 3 votes
# 05AB1E, 4 bytes

```
bR1k

```

Try it online!

```
bR1k  # full program
   k  # get 0-based index of first occurrence of...
  1   # literal...
   k  # in...
      # implicit input...
b     # in binary...
 R    # reversed...
   k  # -1 if not found (this will never happen, as the only time a binary number will not contain 1 is if it is 0 which is not considered as valid input)
      # implicit output

```

# Answer
> 3 votes
# Desmos, 37 characters

Graph link: https://www.desmos.com/calculator/y5lqwruzjp

Before use, make sure `c` is set to 0, and that the first line contains whichever number you want to input. When running, you can either press the metronome button to automatically run the program or press the arrow button to run one iteration of the code.

```
    <input>
    i=ans_0
    c=0
    c->{mod(i,2^(c+1))=0:c+1,c}

```

How it works

1. The `<input>` is the actual number being inputted. For simplicity, it is not counted for characters.
2. `ans_0` reads the 0th line (being the input), and sets `i` to it.
3. `c->` declares an action, which updates `c` to the result.
4. Curly brackets declare a conditional statement. The results are `c+1` if the condition is true, and `c` if not.
5. `mod()` is the modulus command. It divides the first statement by the second, and gives the result.
6. `i`, as mentioned, is the input.
7. `2^(c+1)` is simply `2` raised to `c+1`. The `+1` is used to check the next value of `c`. An exponent is used to repeatedly divide `i` by `2`.
8. `=0` is the condition, used to check if the remainder is equal to `0` (`i` is divisible).

So, the graph first takes `c`, and tries to update it. It raises `2` to `c+1` (to check if the `c` can increment), then divides the input (stored with `i`) by the result and returns the remainder. It then checks if that remainder is equal to `0`, and if so, it sets increments `c` by 1. Otherwise, it doesn't change `c`.

# Answer
> 2 votes
## PowerShell, 36 bytes

```
param($a)for(;!($a%2)){$a/=2;$o++}$o

```

Takes input `$a`, then enters a `for()` loop. There is no setup, but the conditional means the loop ends when `$a` is no longer even. Inside the loop, we just divide `$a` by `2` and increment a counter, then output the counter.

The above correctly accounts for negative numbers (in PowerShell, the `%` operator follows the sign of the dividend, but any non-zero number is truthy, the `!` of which is falsey).

# Answer
> 2 votes
# C, ~~44~~ ~~40~~ 38 36 bytes

2 bytes off thanks @JohnWHSmith. 2 bytes off thanks @luserdroog.

```
a;f(n){for(;~n&1;n/=2)a++;return a;}

```

Test live on ideone.

# Answer
> 2 votes
## JavaScript ES6, 36 38 bytes

Golfed two bytes thanks to @ETHproductions

Fairly boring answer, but it does the job. May actually be too similar to another answer, if he adds the suggested changes then I will remove mine.

```
b=>{for(c=0;b%2-1;c++)b/=2;alert(c)}

```

To run, assign it to a variable (`a=>{for...`) as it's an anonymous function, then call it with `a(100)`.

# Answer
> 2 votes
# CJam, 8 bytes

```
rizmf2e=

```

Read integer, absolute value, prime factorize, count twos.

# Answer
> 2 votes
# Japt, ~~9~~ 5 bytes

```
¢w b1

```

Test it online!

The previous version should have been five bytes, but this one actually works.

### How it works

```
       // Implicit: U = input integer
¢      // Take the binary representation of U.
w      // Reverse.
b1     // Find the first index of a "1" in this string.
       // Implicit output

```

# Answer
> 2 votes
# DUP, 20 bytes

```
[$2/%0=[2/f;!1+.][0]?]f:

```

`Try it here!`

Converted to recursion, output is now the top number on stack. Usage:

```
94208[2/\0=[f;!1+][0]?]f:f;!

```

# Explanation

```
[                ]f: {save lambda to f}
 2/\0=               {top of stack /2, check if remainder is 0}
      [     ][ ]?    {conditional}
       f;!1+         {if so, then do f(top of stack)+1}
              0      {otherwise, push 0}

```

# Answer
> 2 votes
# , 8 chars / 10 bytes

```
ïⓑᴙą1

```

`Try it here (Firefox only).`

# Explanation

Converts input to binary, reverses it, then gets index of first 1.

# Answer
> 2 votes
# Mathematica, 20 bytes

```
#~IntegerExponent~2&

```

Yet another long, un-golfable built-in...

# Answer
> 2 votes
# R, 30 bytes

```
sum(gmp::factorize(scan())==2)

```

Assumes `gmp` package installed

# Answer
> 2 votes
# Oracle SQL 11.2, 111 bytes

```
WITH v(i)AS(SELECT 1 FROM DUAL UNION ALL SELECT i+1 FROM v WHERE MOD(:1/POWER(2,i),1)=0)SELECT MAX(i)-1 FROM v;

```

Un-golfed

```
WITH v(i) AS
(
  SELECT 1 FROM DUAL
  UNION ALL
  SELECT i+1 FROM v WHERE MOD(:1/POWER(2,i),1)=0
)
SELECT MAX(i)-1 FROM v;

```

# Answer
> 2 votes
# PHP, ~~36~~ 28 bytes

Used a different approach than most others. I'm checking divisibility by `2^N` where I'm increasing N until it's no longer divisible by it.

```
for(;0==$argv[1]%2**++$b;);echo$b-1;

```

Run like this (`-d` added for aesthetics only):

```
php -d error_reporting=32757 -r 'for(;0==$argv[1]%2**++$b;);echo$b-1; echo"\n";' -- -65536

```

Implementing orlp's `log` algorithm would be even shorter. I don't like the requirement to create a file for PHP golfs, but this would be the shortest:

```
<?=log(($x=$argv[1])&-$x,2);

```

Edit: I found out you can actually run that without creating a file, by piping it like this:

```
echo '<?=log(($x=$argv[1])&-$x,2);' | php -- -65536

```

# Answer
> 2 votes
# Javascript ES6, 39 chars

```
n=>n.toString(2).match(/0*$/)[0].length

```

Test:

```
[14,20,94208,7,-4].map(n=>n.toString(2).match(/0*$/)[0].length) == "1,2,12,0,2"

```

# Answer
> 2 votes
# Python, 48 chars

```
print len(str(bin(int(input()))).split("1")[-1])

```

Simply counts the number of 0s at the end of the binary number

# Answer
> 2 votes
## R, 56 46 40 bytes

```
x=scan();a=0;while(!x%%2){x=x/2;a=a+1};a

```

Another answer than @mnel's one without the `gmp` package.

Thanks to @user5957401 for saving 10 bytes

Thanks to @Frédéric for saving 6 bytes

# Answer
> 2 votes
# Excel, 20 bytes

Works up to `2^53` (9,007,199,254,740,990)

```
=LOG(GCD(A1,2^53),2)

```

Using Binarys, a 36 byte solution that only works up to 511:

```
=10-FIND(2,DEC2BIN(A2)+DEC2BIN(-A2))

```

# Answer
> 2 votes
# K (ngn/k), ~~9 8 5~~ 7 bytes

```
*&|~~2\

```

Try it online!

# Answer
> 2 votes
# MMIX, 12 bytes (3 instrs)

This is straight out of Knuth volume 4a.

```
27FF0001 DA00FF00 F8010000

```

# Disassembly and explanation

```
rho SUBU $255,$0,1      // tmp = x - 1
    SADD $0,$255,$0     // x = popcnt(tmp & ~x)
    POP  1,0            // return x

```

No, seriously, that's it. An input of 0 gives an output of 64.

# Answer
> 2 votes
# Desmos, 22 bytes

```
f(n)=log_2(gcd(n,2^n))

```

Try It On Desmos!

Doesn't work for `94208` because it's too large for the program. Below is one that supports much more numbers:

### 43 bytes

```
f(n)=log_2(gcd(n,2^{floor(log_2(abs(n)))}))

```

Try It On Desmos!

# Answer
> 2 votes
# Prolog (SWI), ~~39~~ ~~33~~ 32 bytes

```
A-B:-A/\1<1,A//2-D,B is D+1;B=0.

```

Try it online!

*-6 bytes thanks to Jo King!*

*-1 byte thanks to Steffan!*

# Answer
> 2 votes
## C, 23 bytes

```
f(x){x=x&1?0:f(x/2)+1;}

```

Essentially just counts leading 0s recursively.

# Answer
> 1 votes
# Javascript, ~~45~~ ~~39~~ 38 bytes

1 byte off thanks @manatwork.

```
i=>/0*$/.exec(i.toString(2))[0].length

```

```
f=
i=>/0*$/.exec(i.toString(2))[0].length

F=i=>document.body.innerHTML+='<pre>f('+i+') -> '+f(i)+'\n</pre>'

F(14)
F(20)
F(94208)
```

# Answer
> 1 votes
# Java, ~~44~~ 39 bytes

```
int f(int n){return n%2==0?1+f(n/2):0;}

```

Works for odd, zero, and negative numbers.

Golfed 5 bytes because input will not be zero.

# Answer
> 1 votes
## Seriously, 9 bytes

```
,wii2=*.

```

Contains an unprintable (`0x7F`) at the end. Hexdump:

```
2c77 6969 323d 2a2e 7f

```

Try it online!

Explanation:

```
,wii2=*.<0x7F>
,w              get prime factorization of input (list of base, exp pairs)
  ii            flatten first (base, exp) pair so that base, exp is top of stack
    2=*         multiply exponent by 1 if base is 2 else 0
       .<0x7F>  print top item and exit

```

# Answer
> 1 votes
# jq, 26 characters

```
[while(.%2==0;./2)]|length

```

Sample run:

```
bash-4.3$ jq '[while(.%2==0;./2)]|length' <<< 94208
12

bash-4.3$ jq '[while(.%2==0;./2)]|length' <<< -4
2

```

On-line test:

# Answer
> 1 votes
# Perl 6  ~~28~~  27 bytes

```
{($_+&-$_).polymod(2 xx*)-1}
{($_+&-$_).base(2).chars-1}

```

### Usage:

```
my &code = {($_+&-$_).base(2).chars-1}

say code    14; # 1
say code    20; # 2
say code 94208; # 12
say code     7; # 0
say code    -4; # 2

```

# Answer
> 1 votes
## PHP, 40 bytes

```
function e($i){return $i%2?0:e($i/2)+1;}

```

# Answer
> 1 votes
# POSIX shell and GNU/BSD utilities, ~~43~~ 30 bytes

```
factor ${1#-}|rs -T|grep -xc 2

```

We simply count the number of 2s in the output of the `factor` command.

# Answer
> 1 votes
## Pure Bash, 40

If `0` could not be submited as input... Thanks to @TobySpeight for help me to drop a lot.

```
for((o=0;1<<o&~i;++o));do :;done;echo $o

```

### Proof

```
pureBashStr='for((o=0;1<<o&~i;o++));do :;done;echo $o'
echo ${#pureBashStr}
40

for i in 14 20 64#w0000 94208 7 -4 ;do
    printf " %8s: %4d\n" $i $(
        eval $pureBashStr)
  done
       14:    1
       20:    2
 64#w0000:   29
    94208:   12
        7:    0
       -4:    2

```

### +10 to support `0` case: 50

```
pureBashStr='for((o=0;1<<o&~i;o++));do((i))||break;done;echo $o'
i=0
printf " %8s: %4d\n" $i $(eval $pureBashStr)
        0:    0

```

# Answer
> 1 votes
# Groovy, 83 bytes

There was not a groovy answer yet, so here goes. Definitely room for improvement.

```
int n=args[0].toInteger();def e(int n){x=0;while(n%2==0){n/=2;x++;};print x;};e(n);

```

You can use it with: groovy filename.groovy "94208"

# Answer
> 1 votes
**Python 2, 27 bytes**

```
e=lambda n:~n%2and e(n/2)+1

```

In Python 3, you'd have to use `e(n//2)`, since `~` operator doesn't work with floats.

# Answer
> 1 votes
# R, ~~37~~ 35 bytes

```
f=function(n)"if"(n%%2,0,1+f(n/2))

```

Checks if the current number is divisible by two. If not, returns 0, if it is, divides and recursively calls itself again while setting up a counter to add 1.

HT -- Giuseppe for replacing `ifelse` with `"if"` to lose 2 characters

# Answer
> 1 votes
# SmileBASIC, 45 bytes

```
INPUT N@L
IF!(N<<31)THEN N=N>>1Q=Q+!GOTO@L
?Q

```

I'm pretty sure `N<<31` is the shortest way to check the lowest bit in SB, since ` MOD ` and ` AND ` are so long.

# Answer
> 1 votes
# Pure bash, 37 bytes

```
(($1%2))&&echo 0||echo $[1+`$0 $1/2`]

```

A recursive solution.

# Answer
> 1 votes
# BASIC, 36 bytes

```
while(!mod(a,2)):a=a/2:b=b+1:wend:?b

```

Try it online!

It's never going to win, but it's interesting to see how competitive good old fashioned BASIC can be in this sort of thing. I managed to tie with a lot of similar 36 byte solutions in trendier languages like C and Javascript, which is good enough for me.

The implementation is totally straightforward, dividing then incrementing a counter for as long as there is no remainder. I'm sure a more creative solution could reduce this byte count.

I noted that the posted solution algorithms don't account for the actual input, so I've done it as READ/DATA in the header and footer. All the test cases are there - just change the REMark so your desired test has no REM to evaluate. Or put your own "DATA whatever" line and see how my algorithm performs.

# Answer
> 1 votes
# Templates Considered Harmful, 56 bytes

```
Fun<If<Rem<A<1>,I<2>>,F,Add<T,Ap<A<0>,Div<A<1>,I<2>>>>>>

```

Try it online!

Anonymous function that takes an int as input. If it is odd, return 0. Otherwise, add 1 and run function again with input/2.

```
Fun<
    If<Rem<Arg<1>,Int<2>>,
       Int<0>,
       Add<Int<1>,
           Ap<Arg<0>,
              Div<Arg<1>,Int<2>>
           >
       >
    >
>

```

# Answer
> 1 votes
## JavaScript (30 bytes)

A couple of years later, and I've come across another solution after experimenting with bitwise operators. Not the shortest JS answer, but certainly pretty, if you ask me.

```
n=>(-n&n).toString(2).length-1

```

# Answer
> 1 votes
# MathGolf, 4 bytes

```
±â1=

```

Bug-abuse, since it should have been 5 bytes..

Try it online.

**Explanation:**

```
±     # Get the absolute value of the (implicit) input-integer
 â    # Convert it to a reversed list of bits
  1=  # Get the 0-based index of the first 1
      # (after which the entire stack is output implicitly as result)

```

`â` should convert the integer to a binary-list, but instead converts it to a *reversed* binary-list, saving us the need for an explicit `x` to revert it.

# Answer
> 1 votes
# Python 3.8 (pre-release), 50 bytes

```
lambda n: sum(1 for c in bin(n)[::-1] if c=='0')-1

```

Try it online!

# Answer
> 1 votes
# \>\<\>, 13 bytes

```
0$:2,@2%?n1+!

```

Try it online!

**Explanation**

```
   0           !  # initialize evenness as 0 on 1st iteration and skip on subsequent
    $:2,@         # divide a copy of the input by 2 and move to bottom of stack
         2%       # mod the 2nd copy by 2
           ?n     # print evenness if it's true (non-0)
             1+   # increment evenness for next iteration
    $             # error out after printing

```

# Answer
> 1 votes
# Thunno 2, 4 bytes

```
Af2c

```

Attempt This Online!

#### Explanation

```
Af2c  # Implicit input
A     # Get the absolute value
 f    # Push the prime factors
  2c  # Count the 2s
      # Implicit output

```

# Answer
> 1 votes
# Rockstar, 100 bytes

```
listen to N
X's 0
while 1
let M be N/2
turn up M
if M's N/2
build X up
let N be M
else
break

say X

```

Try it (Code will need to be pasted in)

# Answer
> 1 votes
# Julia 0.6, 22 bytes

```
~x=length(bin(x&-x))-1

```

Try it online!

Port of orlp's Python answer. The function `bin` is deprecated in Julia 0.7 and removed in 1.0.

# Answer
> 1 votes
# Nekomata, 2 bytes

```
ˡ½

```

Attempt This Online!

```
ˡ       Apply the following function repeatedly until it fails,
            and count the number of steps
 ½      Check if the input is even, and halve it

```

# Answer
> 1 votes
## Pascal, 78 B

The recursive definition beats the iterative definition *in length*. However, the abort condition `odd(x)` is not guaranteed to be fulfilled for the entire domain of `f`. If `x` is `0`, it is not `odd` and `x div 2` cannot turn `0` into an odd number. Hence in production use you will prefer a `while odd(x)` loop (unless the domain is restricted to *exclude* zero).

```
function f(x:integer):integer;begin if odd(x)then f:=0 else f:=1+f(x div 2)end

```

# Answer
> 0 votes
# Pylons, 22 bytes.

```
:Ai0?Aw[A2A/]1+,2A%1g}

```

Man, this turned out a lot longer than I thought it would.

Turns out it broke on 0 input, so I fixed it.

How it works:

```
:Ai     # Set A equal to command line input.
0       # Push 0 to the stack.
?A      # Check if A is equal to the top of the stack, if so, skip the next instrutction. In this case, the while loop.
w       # Start a while loop.
 [A2A/] # Set A equal to A / 2.
 1+     # Push 1 to the stack and add it to the number at the top of the stack.
 ,      # Switch to loop iteration.
 2A%    # Push A%2 to the loop condition stack.
    1g  # Check if 1 is greater than the top of the loop condition stack.
      } # End the while loop
        # Print the stack at the end of the instruction set.

```

# Answer
> 0 votes
# Whitespace, 109 bytes

Unfortunately I can't put the code here because it gets recognized as formating so this will have to do. http://pastebin.com/cmH30iUF

Try it here: http://ws2js.luilak.net/interpreter.html Just paste the code, type a number, and hit enter.

# Answer
> 0 votes
# MS SQL, 81 bytes

For funsies. `convert( varbinary() )` end up taking more space than the modulo loop.

`create proc p @n int as declare @i int=0while @n%2=0 select @i+=1,@n=@n/2print @i`

Test with

```
p 14;
go
p 20;
go
p 94208;
go
p 7;
go
p -4;
go

```

# Answer
> 0 votes
# dc, 21 bytes

```
#!/usr/bin/dc
?[dd2/r2%0=f]dsfxz2-p

```

Reads the input, then successively divides by 2, building a stack as we go. When we get to an odd number, count the stack depth, adjusting for the odd number and its duplicate.

# Answer
> 0 votes
# Perl 5, 26 bytes

25, plus 1 for `-pe` instead of `-e`.

```
$i++,$_/=2until$_%2;$_=$i

```

or

```
$_=sprintf'%b',$_;s/.*1//

```

(The latter has output in unary.)

# Answer
> 0 votes
# Turing Machine, 53 char

```
   B    1   i

0  B4L  i1R

1  B2L  11R

2       B3L B7L

3           10R

4  B5L

5  16R

6  B0R  16R

7  Bh   B7L

*       1*L
```

It accepts as an input a string of ones and outputs a string of ones. It repeatedly divides the number by 2 and adds 1 to the count after every halving. Try it out here.

# Answer
> 0 votes
## Scala 42 bytes

```
def e(n:Int):Int=if(n%2==0)e(n/2)+1 else 0

```

Similar to Java, but 2 bytes smaller.

# Answer
> 0 votes
# Microscript II, ~~28~~ 27 bytes

```
0s<N[sv2sl%!(.5*v>1+s<l)]>o

```

There's probably still room for improvement here.

# Answer
> 0 votes
# Perl 5 `-p`, 28 bytes

```
$_/=2;/\./||++$\&redo}{$\|=0

```

Try it online!

# Answer
> 0 votes
# Julia 1.5.3

Not sure how to count bytes, but Julia has a built-in function for this.

```
help?> ?trailing_zeros
search: trailing_zeros

  trailing_zeros(x::Integer) -> Integer

  Number of zeros trailing the binary representation of x.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> trailing_zeros(2)
  1

```

Modifying the Python solution gives the following:

```
julia> f=n->length(string(n&-n,base=2))-1
#1 (generic function with 1 method)

julia> f(94208)
12

```

# Answer
> 0 votes
# Perl 5 \+ `-pl060`, 21 bytes

**26 bytes using old rules scoring flags.**

Uses the `-l060` flag to preset `$\` to `0`, and increments it until `$_/=2` is no longer even.

```
$_/=2,++$\until$_%2}{
```

Try it online!

# Answer
> 0 votes
# Japt, 7 bytes

```
v ©ÒßUz

```

Try it

## 4 bytes

Originally had this, but it's the same as ETH's solution.

```
¤Ôb1

```

Try it

## Explanations

```
v ©ÒßUz     :Implicit input of integer U
v           :Divisible by 2? (returns 0 or 1)
  ©         :Logical AND with
   Ò        :Negate the bitwise NOT of
    ß       :Recursive call with argument
     Uz     :  U floor divided by 2

```

---

```
¤Ôb1     :Implicit input of integer U
¤        :Convert to binary string
 Ô       :Reverse
  b1     :First 0-based index of 1

```

# Answer
> 0 votes
# Ly, 41 bytes

```
n0sG2*,*[:2%[lu;]pl`sp:2/r01[p`0IL]p-rpr]

```

Try it online!

Well, this was trickier than I expected... Division in `Ly` yields floating point numbers, which was a challenge for this one. Figuring out how to work around that was fun though. :)

```
n                                         - read the number onto the stack
 0s                                       - init accumulator to 0
   G                                      - push 1 if "n>0"
    2*,                                   - map 0->-1 and 1->0
       *                                  - effectively "n=abs(n)"
        [                               ] - infinite loop
         :2%                              - push 1|0 for "is it odd?"
            [   ]p                        - if odd...
             lu;                          - load accumulator, print and exit
                  l`sp                    - increment accumulator
                      :2/                 - calc number we want (as float)
                         r0               - init "int" result to 0 on bottom of stack
                           1[p    ]p      - loop while to of stack is 1
                              `           - increment "int" result
                               0I         - load "float" result
                                 L        - is "int" < "float"?
                                    -     - decrement "n" by "int" result
                                     rpr  - delete bottom of stack

```

# Answer
> 0 votes
# Commodore C64 BASIC, 86 83 BASIC Bytes used

This method in Commodore BASIC uses the `def fn` function, which is somewhat limited but can be useful. My favourite YouTube Channel 8-BIT Show and Tell talks about this and other *rarely used* commands in some depth here. If you are interested, it's worth mulling over.

```
0deffnm(a)=a-int(a/2)*2:inputx:y=-(fnm(x)=0):ify=0goto2
1x=x/2:iffnm(x)=0theny=y+1:goto1
2printy

```

## How it works

The function that I've defined (referenced as `fnm(x)`) simply acts like a modulus operator in modern days computer programming languages like C and C++. In this instance, we are returning the remainder of any division by 2.

The `inputx` waits for a numeric input, which can be an integer or a floating point number (in fact, Commodore BASIC only really deals with floating point numbers in the ROM, but that's for another time). So note that I've not included a sanity check for floats, nor for `0`, which will be an endless loop.

Once you enter a value, `y=-(fnm(x)=0)` is a short-hand any byte-saving way of `if fn m(x) = 0 then let y = 0: end: else let y = 1`. Note that like many BASIC dialects, Commodore BASIC uses a single equals for assignment and comparison. Commodore BASIC also returns `-1` as `true` and `0` as `false`, as we want to initialise `y` with the value of `1` if the number entered is an even number, so it will divide equally by two at least once. So, now if `y` is `0` and the number entered is odd, then we print it and end.

In line 1, we have a loop which divides the number entered into `x` by 2; if that is even, then we increase the `y` counter by one and go back to the start of line 1 to divide `x` by 2 again, and so on until `x` is odd. On this note the loop ends and `y` is printed.

---
Tags: code-golf, number, division
---


title: Pseudo-Quantum Bogosort

text:
# Question
Title: Pseudo-Quantum Bogosort
## Pseudo-Quantum Bogosort

Quantum Bogosort is as follows:

1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.
2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)
3. All remaining universes contain lists which are sorted.

Source

Given that we cannot destroy the universe, the next best thing is to destroy a thread!

The challenge is as follows: Make a new thread/branch for each possible permutation of a list and if the list is not sorted, destroy the thread/branch (or just dont output it)

## Rules

Input is a list of length 4 or less

Output should be the randomized list for each thread or branch that successfully sorted it. Destroying/exiting the thread or branch is optional, but funny.

If there is a repeated number, output list duplicates.

This is standard code-golf

Test cases:

```
[1,4,2,9] -> [1,2,4,9]
[3,1,1,9] -> [1,1,3,9] and [1,1,3,9]
[3,1,1,3] -> [1,1,3,3] [1,1,3,3] [1,1,3,3] [1,1,3,3]

```

# Answer
# Python, 77 bytes

```
lambda l:[x for x in permutations(l)if[*x]==sorted(x)]
from itertools import*

```

Attempt This Online!
> 2 votes

# Answer
# Husk, 5 bytes

```
fS=OP

```

Try it online!

Quite closely follows the description.

```
    P  # Make a list with an element for each possible permutation of the input list
f      # Destroy (or just don't output) any element that doesn't satisfy:
 S=O   #   it's sorted

```
> 2 votes

# Answer
# Nekomata, ~~3~~ 4 bytes

*Edit: +1 byte to fix (unobservable) mechanism-of-action, thanks to alephalpha.*

```
↕:o=

```

Attempt This Online!

Nekomata seems well-suited for this.
Default behaviour is to output all successful forks.

```
↕      # non-deterministically choose a permutation of the input list
 :     # duplicate it
  o=   # keep one duplicate if it's equal to the other, sorted

```
> 2 votes

# Answer
# Factor \+ `math.combinatorics`, 49 bytes

```
[ <permutations> [ dup sort = ] parallel-filter ]

```

Attempt This Online!

`parallel-filter` is a version of `filter` that spawns cooperative threads to handle each iteration.
> 1 votes

# Answer
# Python 3.8+, 75 bytes

```
lambda a:filter(min(p:=[*permutations(a)]).__eq__,p)
from itertools import*

```

An unnamed function that accepts a tuple and returns a generator.

**Try it online!**

### How?

`a` is the input tuple. `p` is initialised to a list of all permutations of `a`. A condition of being equal to the minimal permutation is then used to create a filter object.

---

Also, non-conforming but interesting at **62 bytes**:

```
lambda a:8**sum(a.count(v)**7-1for v in{*a})%66%26*[sorted(a)]

```

Try it online!

The number of repeats of the sorted list needs to be \\$\prod\_{m \in \text{multiplicities}} m!\\$, e.g. `[5,4,5,5]` has multiplicities `[3,1]` and \\$3!1!=6\\$.

But that's going to cost a lot of bytes. However, since the input has a length of at most four there are only twelve cases to handle by multiplicity, so I thought a hash might be golfier, so I had a play and came up with:

| multiplicities | \**7-1 | sum | 8\**sum%66%26 == required length |
| --- | --- | --- | --- |
| \[\] | \[\] | 0 | 1 |
| \[1\] | \[0\] | 0 | 1 |
| \[2\] | \[127\] | 127 | 2 |
| \[3\] | \[2187\] | 2187 | 6 |
| \[4\] | \[16383\] | 16383 | 24 |
| \[1,1\] | \[0,0\] | 0 | 1 |
| \[1,2\] | \[0,127\] | 127 | 2 |
| \[1,3\] | \[0,2187\] | 2187 | 6 |
| \[2,2\] | \[127,127\] | 254 | 4 |
| \[1,1,1\] | \[0,0,0\] | 0 | 1 |
| \[1,1,2\] | \[0,0,127\] | 127 | 2 |
| \[1,1,1,1\] | \[0,0,0,0\] | 0 | 1 |

...it's certainly shorter than this, more logical, shortcut for lists of length at most four (71):

```
lambda a:(sum((c:=a.count(v))*~-c*-~(c>3)for v in{*a})or 1)*[sorted(a)]

```
> 1 votes

# Answer
# Charcoal, 40 bytes

```
⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻Ｅθνκ⁺κ⟦μ⟧υＦυＵＭι§θκＥΦυ⁼ι⌊υ⭆¹ι

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻Ｅθνκ⁺κ⟦μ⟧υ

```

Generate all of the permutations of the indices of the input. This is taken from my answer to Count N-Rich Permutations of an Integer Sequence. I use the indices because they're unique and it makes it easier to generate the permutations.

```
ＦυＵＭι§θκ

```

Map each index to the actual value from the input list.

```
ＥΦυ⁼ι⌊υ⭆¹ι

```

Pretty print those that equal the minimum i.e. sorted value.
> 1 votes

---
Tags: code-golf, sorting
---