Find the Second Zero

Question

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 code-golf, so the shortest answer in each language wins!

Yes you may, as long as you then handle integers in the range [0, 2^32). — musicman523
– musicman523, Commented Jul 17, 2017 at 15:34
@JonathanAllan I guess not, since I was corrected on my Jelly answer with 2^32-1 because I wasn't supposed to return 33. — Erik the Outgolfer
– Erik the Outgolfer, Commented 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 — musicman523
– musicman523, Commented Jul 17, 2017 at 16:03

Arnold Palmer · Accepted Answer · 2017-07-17 16:23:22Z

16

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.

edited Jul 17, 2017 at 16:23

answered Jul 17, 2017 at 16:18

Arnold Palmer

6033 silver badges8 bronze badges

5

\$\begingroup\$ Welcome to PPCG! Nice first post! \$\endgroup\$

Erik the Outgolfer
– Erik the Outgolfer

2017-07-17 16:26:18 +00:00
Commented Jul 17, 2017 at 16:26
\$\begingroup\$ Thanks! I'm still really new to golfing trickery in Python, so I'm glad this code didn't get golfed down immediately. \$\endgroup\$

Arnold Palmer
– Arnold Palmer

2017-07-17 16:31:27 +00:00
Commented Jul 17, 2017 at 16:31
\$\begingroup\$ Great :) what about n=2147483647? \$\endgroup\$

mdahmoune
– mdahmoune

2017-07-17 16:44:54 +00:00
Commented Jul 17, 2017 at 16:44
\$\begingroup\$ @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... \$\endgroup\$

Arnold Palmer
– Arnold Palmer

2017-07-17 16:51:22 +00:00
Commented Jul 17, 2017 at 16:51

Add a comment |

Arnauld · Accepted Answer · 2017-07-18 10:00:47Z

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
– Neil, Commented Jul 17, 2017 at 18:55

jimmy23013 · Accepted Answer · 2017-07-18 10:32:54Z

5

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).

edited Jul 18, 2017 at 10:32

answered Jul 17, 2017 at 17:20

jimmy23013

37.4k6 gold badges79 silver badges154 bronze badges

1

\$\begingroup\$ -inf+nanj I didn't think that could even exist \$\endgroup\$

Luis Mendo
– Luis Mendo

2017-07-17 21:46:27 +00:00
Commented Jul 17, 2017 at 21:46
\$\begingroup\$ 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). \$\endgroup\$

Jonathan Allan
– Jonathan Allan

2017-07-17 23:30:12 +00:00
Commented Jul 17, 2017 at 23:30
\$\begingroup\$ Actually, when does it produce (-inf+nanj)? \$\endgroup\$

Jonathan Allan
– Jonathan Allan

2017-07-17 23:32:40 +00:00
Commented Jul 17, 2017 at 23:32
\$\begingroup\$ ...ah I think worked it out, you're using the signed option? \$\endgroup\$

Jonathan Allan
– Jonathan Allan

2017-07-17 23:42:18 +00:00
Commented Jul 17, 2017 at 23:42

Add a comment |

anatolyg · Accepted Answer · 2017-07-18 12:29:03Z

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:

No zero bits (binary 111...1): ecx is set to 0 by not and remains 0
One zero bit: ecx is set to 0 by btr and remains 0 after bsf
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. — Cody Gray
– Cody Gray, Commented 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 — Cody Gray
– Cody Gray, Commented 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. — Cody Gray
– Cody Gray, Commented Jul 18, 2017 at 11:22

Nevay · Accepted Answer · 2017-07-19 02:41:58Z

Java (OpenJDK 8), 44 38 bytes

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

Try it online!

Returns 0 if no second zero bit exists.

0x45 · Accepted Answer · 2017-07-18 14:30:21Z

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! :) — Kevin Cruijssen
– Kevin Cruijssen, Commented Jul 18, 2017 at 11:55
I think there are still a couple spaces you can remove in your variable declarations. Welcome! :) — musicman523
– musicman523, Commented Jul 18, 2017 at 13:18
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. — Kevin Cruijssen
– Kevin Cruijssen, Commented 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. — Arnold Palmer
– Arnold Palmer, Commented Jul 18, 2017 at 14:11

Uriel · Accepted Answer · 2017-07-17 16:05:27Z

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

\$\begingroup\$ You could save a lot of bytes using Where (⍸) \$\endgroup\$

TwiN
– TwiN

2017-07-17 23:12:09 +00:00
Commented Jul 17, 2017 at 23:12 — TwiN
– TwiN, Commented Jul 17, 2017 at 23:12
\$\begingroup\$ @TwiNight I use dyalog 14 \$\endgroup\$

Uriel
– Uriel

2017-07-18 12:22:46 +00:00
Commented Jul 18, 2017 at 12:22 — Uriel
– Uriel, Commented Jul 18, 2017 at 12:22
\$\begingroup\$ TIO has Dyalog 16 if you need \$\endgroup\$

TwiN
– TwiN

2017-07-18 12:34:52 +00:00
Commented Jul 18, 2017 at 12:34 — TwiN
– TwiN, Commented Jul 18, 2017 at 12:34

Erik the Outgolfer · Accepted Answer · 2017-07-17 16:12:14Z

1

Jelly, 13 bytes

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

Try it online!

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

edited Jul 17, 2017 at 16:12

answered Jul 17, 2017 at 15:41

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

\$\begingroup\$ This outputs 33 for the input 4294967295 (2^32-1, the 32-bit unsigned equivalent of -1) \$\endgroup\$

musicman523
– musicman523

2017-07-17 15:44:05 +00:00
Commented Jul 17, 2017 at 15:44
\$\begingroup\$ @musicman523 Hmm, something smells fishy... \$\endgroup\$

Erik the Outgolfer
– Erik the Outgolfer

2017-07-17 15:46:13 +00:00
Commented Jul 17, 2017 at 15:46

Add a comment |

Jonathan Allan · Accepted Answer · 2017-07-17 16:42:34Z

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] Ḣ - head 5 - 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] Ḣ - head 5 - if the dequeued list is empty the head yields 0

ბიმო · Accepted Answer · 2017-07-18 14:38:54Z

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 add %edx, %ecx # 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 — Cody Gray
– Cody Gray, Commented 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. — Cody Gray
– Cody Gray, Commented Jul 18, 2017 at 11:09

Giuseppe · Accepted Answer · 2017-07-18 20:08:01Z

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!

Chaos Manor · Accepted Answer · 2017-07-18 20:51:47Z

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

NoLongerBreathedIn · Accepted Answer · 2021-05-02 14:36:53Z

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.

Stack Exchange Network

Find the Second Zero

Challenge

Test Cases

Scoring

13 Answers 13

Python 2, 45 bytes

JavaScript (ES6), 34 bytes

Test cases

Alternate expression

Recursive version, 42 bytes

How?

Test cases

Alternate version suggested by Neil, 41 bytes

Jelly, 7 bytes

IA-32 machine code, 14 13 bytes

Java (OpenJDK 8), 44 38 bytes

Java, ... 194 191 186 Bytes

Ungolfed

Dyalog APL, 20 bytes

Jelly, 13 bytes

Jelly, 12 bytes

How?

x86_64 machine code, 34 32 bytes

R, 66 bytes

8th, 149 bytes

MMIX, 20 bytes (5 instrs)

Hot Network Questions

Find the Second Zero

Challenge

Test Cases

Scoring

13 Answers 13

Python 2, 45 bytes

JavaScript (ES6), 34 bytes

Test cases

Alternate expression

Recursive version, 42 bytes

How?

Test cases

Alternate version suggested by Neil, 41 bytes

Jelly, 7 bytes

IA-32 machine code, 14 13 bytes

Java (OpenJDK 8), 44 38 bytes

Java, ... 194 191 186 Bytes

Ungolfed

Dyalog APL, 20 bytes

Jelly, 13 bytes

Jelly, 12 bytes

How?

x86_64 machine code, 34 32 bytes

R, 66 bytes

8th, 149 bytes

MMIX, 20 bytes (5 instrs)

Related

Hot Network Questions