10
\$\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!

\$\endgroup\$
  • \$\begingroup\$ Can we use an unsigned integer instead? \$\endgroup\$ – Leaky Nun Jul 17 '17 at 15:32
  • \$\begingroup\$ Yes you may, as long as you then handle integers in the range [0, 2^32). \$\endgroup\$ – musicman523 Jul 17 '17 at 15:34
  • 1
    \$\begingroup\$ Are we taking the integer or the string 0b... as input? \$\endgroup\$ – TheLethalCoder Jul 17 '17 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 '17 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 '17 at 16:03

12 Answers 12

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.

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

\$\endgroup\$
  • 1
    \$\begingroup\$ -inf+nanj I didn't think that could even exist \$\endgroup\$ – Luis Mendo Jul 17 '17 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 '17 at 23:30
  • \$\begingroup\$ Actually, when does it produce (-inf+nanj)? \$\endgroup\$ – Jonathan Allan Jul 17 '17 at 23:32
  • \$\begingroup\$ ...ah I think worked it out, you're using the signed option? \$\endgroup\$ – Jonathan Allan Jul 17 '17 at 23:42
4
\$\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;
}
\$\endgroup\$
  • \$\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 '17 at 11:55
  • \$\begingroup\$ I think there are still a couple spaces you can remove in your variable declarations. Welcome! :) \$\endgroup\$ – musicman523 Jul 18 '17 at 13:18
  • \$\begingroup\$ @musicman523 Thanks, yeah fixed it. 194 for now :) \$\endgroup\$ – 0x45 Jul 18 '17 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 '17 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 '17 at 14:11
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.

\$\endgroup\$
3
\$\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
\$\endgroup\$
  • \$\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 Jul 18 '17 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 Jul 18 '17 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 Jul 18 '17 at 11:22
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

\$\endgroup\$
  • \$\begingroup\$ You could save a lot of bytes using Where () \$\endgroup\$ – TwiNight Jul 17 '17 at 23:12
  • \$\begingroup\$ @TwiNight I use dyalog 14 \$\endgroup\$ – Uriel Jul 18 '17 at 12:22
  • \$\begingroup\$ TIO has Dyalog 16 if you need \$\endgroup\$ – TwiNight Jul 18 '17 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.

\$\endgroup\$
  • \$\begingroup\$ This outputs 33 for the input 4294967295 (2^32-1, the 32-bit unsigned equivalent of -1) \$\endgroup\$ – musicman523 Jul 17 '17 at 15:44
  • \$\begingroup\$ @musicman523 Hmm, something smells fishy... \$\endgroup\$ – Erik the Outgolfer Jul 17 '17 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
\$\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.

\$\endgroup\$
  • 1
    \$\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 Jul 18 '17 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 Jul 18 '17 at 11:09
1
\$\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
\$\endgroup\$
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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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