12
\$\begingroup\$

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!

Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ Can we use an unsigned integer instead? \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 15:32
  • \$\begingroup\$ Yes you may, as long as you then handle integers in the range [0, 2^32). \$\endgroup\$
    – musicman523
    Jul 17, 2017 at 15:34
  • 1
    \$\begingroup\$ Are we taking the integer or the string 0b... as input? \$\endgroup\$
    – TheLethalCoder
    Jul 17, 2017 at 15:41
  • 1
    \$\begingroup\$ @JonathanAllan I guess not, since I was corrected on my Jelly answer with 2^32-1 because I wasn't supposed to return 33. \$\endgroup\$
    – Erik the Outgolfer
    Jul 17, 2017 at 15:57
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – musicman523
    Jul 17, 2017 at 16:03

13 Answers 13

Reset to default
16
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • 5
    \$\begingroup\$ Welcome to PPCG! Nice first post! \$\endgroup\$
    – Erik the Outgolfer
    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
    Jul 17, 2017 at 16:31
  • \$\begingroup\$ Great :) what about n=2147483647? \$\endgroup\$
    – mdahmoune
    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
    Jul 17, 2017 at 16:51
6
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 41-byte recursive version: f=(n,c=1)=>n%2?1+f(~-n/2,c):c&&1+f(n/2,0) \$\endgroup\$
    – Neil
    Jul 17, 2017 at 18:55
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ -inf+nanj I didn't think that could even exist \$\endgroup\$
    – Luis Mendo
    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
    Jul 17, 2017 at 23:30
  • \$\begingroup\$ Actually, when does it produce (-inf+nanj)? \$\endgroup\$
    – Jonathan Allan
    Jul 17, 2017 at 23:32
  • \$\begingroup\$ ...ah I think worked it out, you're using the signed option? \$\endgroup\$
    – Jonathan Allan
    Jul 17, 2017 at 23:42
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Cody Gray - on strike
    Jul 18, 2017 at 10:34
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Cody Gray - on strike
    Jul 18, 2017 at 11:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Cody Gray - on strike
    Jul 18, 2017 at 11:22
4
\$\begingroup\$

Java (OpenJDK 8), 44 38 bytes

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

Try it online!

Returns 0 if no second zero bit exists.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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;
}
Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ 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! :) \$\endgroup\$
    – Kevin Cruijssen
    Jul 18, 2017 at 11:55
  • \$\begingroup\$ I think there are still a couple spaces you can remove in your variable declarations. Welcome! :) \$\endgroup\$
    – musicman523
    Jul 18, 2017 at 13:18
  • \$\begingroup\$ @musicman523 Thanks, yeah fixed it. 194 for now :) \$\endgroup\$
    – 0x45
    Jul 18, 2017 at 13:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Kevin Cruijssen
    Jul 18, 2017 at 13:34
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Arnold Palmer
    Jul 18, 2017 at 14:11
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You could save a lot of bytes using Where (⍸) \$\endgroup\$
    – TwiNight
    Jul 17, 2017 at 23:12
  • \$\begingroup\$ @TwiNight I use dyalog 14 \$\endgroup\$
    – Uriel
    Jul 18, 2017 at 12:22
  • \$\begingroup\$ TIO has Dyalog 16 if you need \$\endgroup\$
    – TwiNight
    Jul 18, 2017 at 12:34
1
\$\begingroup\$

Jelly, 13 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This outputs 33 for the input 4294967295 (2^32-1, the 32-bit unsigned equivalent of -1) \$\endgroup\$
    – musicman523
    Jul 17, 2017 at 15:44
  • \$\begingroup\$ @musicman523 Hmm, something smells fishy... \$\endgroup\$
    – Erik the Outgolfer
    Jul 17, 2017 at 15:46
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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 \$\endgroup\$
    – Cody Gray - on strike
    Jul 18, 2017 at 10:36
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Cody Gray - on strike
    Jul 18, 2017 at 11:09
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.