# Challenge

Given an integer in 32-bit two's complement format, return the index of the second least-significant zero digit in the binary representation, where an index of 0 represents the least significant bit, and an index of 31 represents the most significant bit.

If there is no second zero, you may return 0, any negative number, any falsy value, or report an error in a way that makes sense in your language.

You may use 1-indexing if you prefer, but the test cases below will use 0-indexing.

You may use unsigned integers if you prefer; if you do, then you must handle integers in the range [0, 2^32). If you use signed integers, you must handle integers in the range [-2^31, 2^31). The test cases here will use signed integers, but note that -x (signed) is 2^32 - x (unsigned).

# Test Cases

0  (0b00)        -> 1
1  (0b001)       -> 2
10 (0b1010)      -> 2
11 (0b01011)     -> 4
12 (0b1100)      -> 1
23 (0b010111)    -> 5
-1 (0b11..11)    -> None
-2 (0b11..10)    -> None
-4 (0b11..00)    -> 1
-5 (0b11..1011)  -> None
-9 (0b11..10111) -> None
2^31-2 (0b0111..1110) -> 31

# Scoring

This is , so the shortest answer in each language wins!

• Can we use an unsigned integer instead? Jul 17, 2017 at 15:32
• Yes you may, as long as you then handle integers in the range [0, 2^32). Jul 17, 2017 at 15:34
• Are we taking the integer or the string 0b... as input? Jul 17, 2017 at 15:41
• @JonathanAllan I guess not, since I was corrected on my Jelly answer with 2^32-1 because I wasn't supposed to return 33. Jul 17, 2017 at 15:57
• @JonathanAllan Erik's answer is correct. I've updated the challenge spec to reflect that you should handle 32-bit integers whether you choose to take them as signed or unsigned Jul 17, 2017 at 16:03

# Python 2, 45 bytes

lambda n:[i for i in range(32)if n|1<<i>n][1]

Try it online!

Uses 0-indexing, unsigned numbers, and throws an error on no second zero.

Simply creates a list of indices of non-set bits, from lowest to highest, and returns the second entry.

• Welcome to PPCG! Nice first post! Jul 17, 2017 at 16:26
• Thanks! I'm still really new to golfing trickery in Python, so I'm glad this code didn't get golfed down immediately. Jul 17, 2017 at 16:31
• Great :) what about n=2147483647? Jul 17, 2017 at 16:44
• @mdahmoune 2**31-1 should error out since its binary representation in 32 bits is 0b01111111111111111111111111111111, which doesn't have a second 0. Unless I'm missing something... Jul 17, 2017 at 16:51

## JavaScript (ES6), 34 bytes

Returns a 0-based index, or -1 if no second zero is found.

n=>31-Math.clz32((n=~n^~n&-~n)&-n)

### Test cases

let f =

n=>31-Math.clz32((n=~n^~n&-~n)&-n)

console.log(f(0))       // -> 1
console.log(f(1))       // -> 2
console.log(f(10))      // -> 2
console.log(f(11))      // -> 4
console.log(f(12))      // -> 1
console.log(f(23))      // -> 5
console.log(f(-1))      // -> None
console.log(f(-2))      // -> None
console.log(f(-4))      // -> 1
console.log(f(-5))      // -> None
console.log(f(-9))      // -> None
console.log(f(2**31-2)) // -> 31

### Alternate expression

n=>31-Math.clz32((n=~n^++n&-n)&-n)

## Recursive version, 42 bytes

Returns a 0-based index, or false if no second zero is found.

f=(n,p=k=0)=>n&1||!k++?p<32&&f(n>>1,p+1):p

### How?

f=(n,p=k=0)=>                               // given n, p, k
n&1||                          // if the least significant bit of n is set
!k++?                     // or this is the 1st zero (k was not set):
p<31&&               //   return false if p is >= 31
f(n>>1,p+1)    //   or do a recursive call with n>>1 / p+1
:p  // else: return p

### Test cases

f=(n,p=k=0)=>n&1||!k++?p<32&&f(n>>1,p+1):p

console.log(f(0))       // -> 1
console.log(f(1))       // -> 2
console.log(f(10))      // -> 2
console.log(f(11))      // -> 4
console.log(f(12))      // -> 1
console.log(f(23))      // -> 5
console.log(f(-1))      // -> None
console.log(f(-2))      // -> None
console.log(f(-4))      // -> 1
console.log(f(-5))      // -> None
console.log(f(-9))      // -> None
console.log(f(2**31-2)) // -> 31

### Alternate version suggested by Neil, 41 bytes

Returns a 0-based index, or throws a too much recursion error if no second zero is found.

f=(n,c=1)=>n%2?1+f(~-n/2,c):c&&1+f(n/2,0)
• 41-byte recursive version: f=(n,c=1)=>n%2?1+f(~-n/2,c):c&&1+f(n/2,0)
– Neil
Jul 17, 2017 at 18:55

# Jelly, 7 bytes

|‘‘&~l2

Try it online!

It outputs something not in the range [1,31] if there isn't the second zero. This includes 32 33 and (-inf+nanj). I guess that makes some sense.

It calculates log(((x|(x+1))+1)&~x)/log(2).

• -inf+nanj I didn't think that could even exist Jul 17, 2017 at 21:46
• It does not output (-inf+nanj) for an input of 2147483647 which has a binary representation of 31 1s, hence no second zero in 32-bit signed notation (this is why it's so much shorter than mine and Erik's answers). Jul 17, 2017 at 23:30
• Actually, when does it produce (-inf+nanj)? Jul 17, 2017 at 23:32
• ...ah I think worked it out, you're using the signed option? Jul 17, 2017 at 23:42

# IA-32 machine code, 14 13 bytes

Hexdump:

F7 D1 0F BC C1 0F B3 C1 0F BC C9 91 C3

Disassembly listing:

0:  f7 d1                   not    ecx
2:  0f bc c1                bsf    eax,ecx
5:  0f b3 c1                btr    ecx,eax
8:  0f bc c1                bsf    ecx,ecx
b:  91                      xchg   eax, ecx
c:  c3                      ret

Receives input in ecx; output is in al. Returns 0 on error.

First of all, it inverts the input, so it can use the bit scan instructions to look for set bits. It looks for the least significant set bit, resets it, looks for least significant set bit again, and returns the result.

If the bit-scan instruction doesn't find any set bit, the Intel documentation says the output is undefined. However, in practice all processors leave the destination register unchanged in this case (as noted by Cody Gray, AMD documentation describes this behavior as mandatory).

So, there are the following cases:

1. No zero bits (binary 111...1): ecx is set to 0 by not and remains 0
2. One zero bit: ecx is set to 0 by btr and remains 0 after bsf
3. Two zero bits: ecx is set to the proper value by bsf
• It is only Intel's documentation that says bit scans on 0 are undefined. AMD's documentation explicitly documents that the destination is unchanged. If you want to avoid this behavior, you would normally add the REP prefix to get either LZCNT or TZCNT, but that increases the byte count, which is naturally undesirable for code golf. Jul 18, 2017 at 10:34
• You're actually doing too much work here. The challenge doesn't require you to discriminate between the case where there are no zero bits and the case where there's only 1 zero bit. It allows you to return 0 (or any negative value) in both cases. So, although the 1-byte SALC+DEC is extremely clever, you can shave off a byte by just using whatever is in ECX as of the second BSF instruction. The only thing that requires is a 1-byte XCHG to get the result in EAX so it can be returned. In other words, not ecx; bsf eax, ecx; btr ecx, eax; bsf ecx, ecx; xchg eax, ecx; ret Jul 18, 2017 at 11:19
• Here's a "try it online" link for the above. Since you're using ECX as the input register, we need to tell GCC to use the fastcall calling convention. Jul 18, 2017 at 11:22

# Java (OpenJDK 8), 44 38 bytes

i->i.numberOfTrailingZeros(~i&-i-2)&31

Try it online!

Returns 0 if no second zero bit exists.

# Java, ... 194 191 186 Bytes

static int f(int n){char[] c=Integer.toBinaryString(n).toCharArray();int j=0,o=2^32-2,i=c.length,l=i-1;if(n<0|n>o)return 0;for(;j<2&i>0;j+=c[--i]==48?1:0);if(j==2)return l-i;return 0;}

-159 Bytes for using smaller variable names and removing whitespace
-25 Bytes, after taking even shorter variables and thanks to @KevinCruijssen tips
-18 Bytes, more whitespaces, function name
-3 Bytes, thanks to @KevinCruijssen, shortening if condition
-5 Bytes, Thanks to @Arnold Palmer, @KevinCruijssen, shortening loop

## Ungolfed

public static int getPosSecondZero2(int number){
int overflow = 2^32-2;
if(number < 0 || number > overflow){
return 0;
}
String binaryString = Integer.toBinaryString(number);
char[] binaryCharArray = binaryString.toCharArray();
int count = 0;
int idx = binaryCharArray.length;
int length = binaryCharArray.length -1;
while(count < 2 && idx>0){
idx--;
if(binaryCharArray[idx] == '0'){
count++;
}
}
if(count == 2)
return length-idx;
return 0;
}
• Welcome to PPCG! There are quite a few things you can golf: static can be removed; if(n<0||n>o){return 0;}can be if(n<0|n>o)return 0; (| instead of || and no brackets); bs, bsa, etc. can all be single characters (never use multi-byte variable/method names in code-golf); You can combine ints, like this: int o=2^32-2,c=0,i=x.length,l=i-1;. And there are some more things to golf. Tips for golfing in Java and Tips for golfing in all languages might be interesting to read. Again welcome, and enjoy your stay! :) Jul 18, 2017 at 11:55
• I think there are still a couple spaces you can remove in your variable declarations. Welcome! :) Jul 18, 2017 at 13:18
• @musicman523 Thanks, yeah fixed it. 194 for now :)
– 0x45
Jul 18, 2017 at 13:23
• if(c[i]=='0'){j++;} can still be golfed to if(c[i]==48)j++; for -3 bytes :) EDIT: Or better yet: while(j<2&&i>0){i--;if(c[i]=='0'){j++;}} can be for(;j<2&i>0;j+=c[i--]==48?1:0); for -8 bytes. Jul 18, 2017 at 13:34
• @0x45 I believe if you change @KevinCruijssen's code to for(;j<2&i>0;j+=c[--i]==48?1:0); it should work. The error is coming from i being the length of the string, so initially you're trying to index past the bounds of the array. If you do a pre-decrement (as shown in the updated snippet), then the first time you use it it will access c[c.length-1] like in your original code. Jul 18, 2017 at 14:11

# Dyalog APL, 20 bytes

{2⊃(⍳32)/⍨~⌽⍵⊤⍨32⍴2}

Uses 1-indexing, throws INDEX ERROR in case of no second zero.

How?

⍵⊤⍨ - encode as a

32⍴2 - binary string of length 32

- reverse

~ - negate (0→1, 1→0)

(⍳32)/⍨ - compress with the range 1-32 (leaving indexes of zeros)

2⊃ - pick the second element

• You could save a lot of bytes using Where () Jul 17, 2017 at 23:12
• @TwiNight I use dyalog 14 Jul 18, 2017 at 12:22
• TIO has Dyalog 16 if you need Jul 18, 2017 at 12:34

# Jelly, 13 bytes

B¬Ṛ;1,1ḣ32TḊḢ

Try it online!

Uses 1-indexing, gets unsigned integer as input. Returns 0 for not found.

• This outputs 33 for the input 4294967295 (2^32-1, the 32-bit unsigned equivalent of -1) Jul 17, 2017 at 15:44
• @musicman523 Hmm, something smells fishy... Jul 17, 2017 at 15:46

# Jelly, 12 bytes

,4BUFḣ32¬TḊḢ

A monadic link, taking an integer, using the unsigned option and returning the 1-indexed result (returns 0 when none exists).

Try it online!

or

32Ḷ2*|€n⁸TḊḢ

Try that

### How?

1.

,4BUFḣ32¬TḊḢ - Link: number, n   e.g. 14
,4           - pair with 4            [14,4]
B          - to binary              [[1,1,1,0],[1,0,0]]
U         - upend                  [[0,1,1,1],[0,0,1]]
F        - flatten                [0,1,1,1,0,0,1]
ḣ32     - head to 32             [0,1,1,1,0,0,1] (truncates the right if need be)
¬    - not (vectorises)       [1,0,0,0,1,1,0]
T   - truthy indexes         [1,5,6]
Ḋ  - dequeue                [5,6]
-   if the dequeued list is empty the head yields 0

2.

32Ḷ2*|€n⁸TḊḢ - Link: number, n   e.g. 14
32Ḷ          - lowered range of 32    [ 0, 1, 2, 3, 4, 5, ...,31]
2*        - 2 exponentiated        [ 1, 2, 4, 8,16,32, ...,2147483648]
|€      - bitwise or for €ach    [15,14,14,14,30,46, ...,2147483662]
⁸    - chain's right argument 14
n     - not equal?             [ 1, 0, 0, 0, 1, 1, ..., 1]
T   - truthy indexes         [ 1, 5, 6, ..., 32]
Ḋ  - dequeue                [ 5, 6, ..., 32]
-   if the dequeued list is empty the head yields 0

# x86_64 machine code, 34 32 bytes

Not sure if this is the right approach, quite a lot of bytes (turns out it is not):

31 c0 83 c9 ff 89 fa 83 e2 01 83 f2 01 01 d1 7f 09 ff c0 d1 ef eb ee 83 c8 ff 83 f8 1f 7f f8 c3

Try it online!

second_zero:
# Set eax = 0
xor  %eax, %eax
# Set ecx = -1
xor %ecx,%ecx
not %ecx

# Loop over all bits
Loop:
# Get current bit
mov %edi, %edx
and $0x1, %edx # Check if it's zero and possibly increment ecx xor$0x1, %edx
# If ecx > 0: we found the position & return
jg Return
# Increment the position
inc %eax
# Shift the input and loop
shr %edi
jmp Loop

Fix:
# If there's not two 0, set value to -1
xor %eax,%eax
not %eax

Return:
# Nasty fix: if position > 31 (e.g for -1 == 0b11..11)
cmp $31, %eax jg Fix ret Thanks @CodyGray for -2 bytes. • Looping through all of the bits is probably not the right approach, either for code golfing or for real world. The real breakthrough will be using one of the instructions that allow you to manipulate all 32 (or 64) bits at once, like BSF, BSR, POPCNT, BT, etc. Anatolyg has submitted a solution along these lines. I haven't yet determined if it can be beat. :-p Jul 18, 2017 at 10:36 • By the way, a potentially useful code-golfing trick to set a register to -1 is to OR it with -1. For example, or ecx, -1. That's 3 bytes, 1 byte shorter than XOR+NEG. This isn't a good trick when not golfing because it introduces a false read dependency on the destination register, but there you'd just use mov ecx, -1 and spend the 5 bytes. Jul 18, 2017 at 11:09 # R, 66 bytes w=which.min x=strtoi(intToBits(scan()));w(x[-w(x)])*any(!x[-w(x)]) reads from stdin; returns 0 for no second zero and the place otherwise. Try it online! # 8th, 149 bytes 2 base swap >s nip decimal s:len 32 swap n:- ( "0" s:<+ ) swap times s:rev null s:/ a:new swap ( "0" s:= if a:push else drop then ) a:each swap 1 a:@ Commented code : f \ n -- a1 a2 n \ decimal to binary conversion 2 base swap >s nip decimal \ 32bit formatting (padding with 0) s:len 32 swap n:- ( "0" s:<+ ) swap times \ put reversed binary number into an array s:rev null s:/ \ build a new array with position of each zero a:new swap ( "0" s:= if a:push else drop then ) a:each \ put on TOS the position of the 2nd least least-significant zero digit swap 1 a:@ ; Usage and output ok> : f 2 base swap >s nip decimal s:len 32 swap n:- ( "0" s:<+ ) swap times s:rev null s:/ a:new swap ( "0" s:= if a:push else drop then ) a:each swap 1 a:@ ; ok> [0, 1, 10, 11, 12, 23, -1, -2, -4, -5, -9, 2147483646] ok> ( dup . " -> " . f . 2drop cr ) a:each 0 -> 1 1 -> 2 10 -> 2 11 -> 4 12 -> 1 23 -> 5 -1 -> null -2 -> null -4 -> 1 -5 -> null -9 -> null 2147483646 -> 31 # MMIX, 20 bytes (5 instrs) xxd --jelly 00000000: 23ff0001 c00000ff 23ff0001 da00ff00 #”¡¢Ċ¡¡”#”¡¢ḷ¡”¡ 00000010: fe010000 “¢¡¡ Disassembly sndz ADDU$255,$0,1 OR$0,$0,$255     // x |= x + 1
ADDU $255,$0,1
SADD $0,$255,\$0     // x = popcnt((x + 1) & ~x)
POP  1,0

The algorithm is essentially the obvious "remove rightmost 0; figure out position of rightmost 0". The neat trick here is that I managed to do it without flipping all the bits first.