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

>>42
Nice work, only takes 15 seconds to precompute all reasonable values of n up to int_max.

#include <x86intrin.h>

int buffer[2147483647];

int bingap32_dc(int N) {
int maxGap=0,gap=0;
do {
N >>= __builtin_ctz(N);
N >>= __builtin_ctz(~N);
maxGap = gap>maxGap?gap:maxGap;
gap = __builtin_ctz(N);
} while(N);

return maxGap;
}

int solution(int N) {
return buffer[N];
}

int main() {

for (int n=0; n<2147483647; n++)
buffer[n] = bingap32_dc(n);

for (int n=0; n<10; n++)
solution(n);

return 0;
}

This'll turn solution into O(1)