[PROG CHALLENGE #024] Non-Corporate Edition

Write a function:

int solution(int N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

A 32-bit version to directly compare with Cudder asm.bingap32():
12c0: 31 c9 xor %ecx,%ecx
12c2: 31 c0 xor %eax,%eax
12c4: ba ff ff ff ff mov $0xffffffff,%edx
12c9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
12d0: 39 c8 cmp %ecx,%eax
12d2: 0f 4c c1 cmovl %ecx,%eax
12d5: 0f bc cf bsf %edi,%ecx
12d8: 0f 44 ca cmove %edx,%ecx
12db: ff c1 inc %ecx
12dd: d3 ef shr %cl,%edi
12df: 0f bc cf bsf %edi,%ecx
12e2: d3 ef shr %cl,%edi
12e4: 85 ff test %edi,%edi
12e6: 75 e8 jne 12d0 <bingap32+0x10>
12e8: c3 retq
12e9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)



int bingap32(unsigned int N){// a faster pure C bingap using GCC intrinsics
int maxGap=0,gap=0;
do{
maxGap=gap>maxGap?gap:maxGap;//if N has bits set maxGap(initial iteration does nothing)
N>>=__builtin_ffs(N);//strip trailing ones
gap=__builtin_ctz(N);//count trailing zeros
N>>=gap;//strip trailing zeros (Maxgap set at next iteration)
}while(N);
return maxGap;
}