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

>>37
>>38
>>39
Chad too

Managed to squeeze even more cycles by moving cmove to the end.
//delayed compare version
int bingap32_dc(u32 N){// a faster pure C bingap using GCC intrinsics
int maxGap=0,gap=0;//905887818 cycles(see http://void.wikidot.com/code:bingap-c )
do{
N>>=__builtin_ctz(N);//strip trailing zeros
N>>=__builtin_ctz(~N);//strip trailing ones
maxGap=gap>maxGap?gap:maxGap;//if N has bits set maxGap(initial iteration does nothing)
gap=__builtin_ctz(N);//count trailing zeros
}while(N);

return maxGap;
}

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

>>36
Only if you believe the marketing...

>>43
Enjoy your RAM latency, lol.

No compiler so far has managed to beat 24 bytes.

>>43
1.Bingap functions operate with unsigned ints.
2.only 5bits are needed to store 32bit binary gap which is 6.4 times less than int(32).
3.calculating int_max binary gaps each time the program starts negates any performance benefits.
4.hardware with less than 8GB will either swap to disk or crash.
5.Uncached RAM access will cause cache flushes as you attempt to read random values from the array.
https://stackoverflow.com/questions/1756825/how-can-i-do-a-cpu-cache-flush-in-x86-windows "The wbinvd instruction takes on the order of 2000-5000 clock cycles to complete!"

>>45

3.calculating int_max binary gaps each time the program starts negates any performance benefits.

Nonsense, it's simply trading space complexity and initial compute time to get O(1) on reads. This approach is pretty common in large scale distributed programming.

4.hardware with less than 8GB will either swap to disk or crash.

It's not 1970 and memory doesn't cost an arm and a leg anymore.

If you still don't believe memory lookup tables can be used for performance please see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable and/or a modern project like Apache Spark.

>>46
Lookup tables are ok, bit they have to fit in cache(preferably L1) and i have only 7.68GB of ram(*some of 8GB reserved to graphics) and manually disabled all forms of swap.
total used free shared buff/cache available
Mem: 7668728 1923568 3879500 277244 1865660 5648868
Swap: 0 0 0

That Rust solution gave me an itch.

//gcc -std=c99 -Ofast -march=native -mtune=native -pthread
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

const int MAX_INT = 2147483647;
int buffer[MAX_INT];
int numCPU = 1;

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];
}

void* worker(void *arg) {

int id = (int)arg;
int chunk = (MAX_INT / numCPU);
int start = chunk * id;
int stop = start + chunk;

for (int i = start; i < stop; ++i) {
buffer[i] = bingap32_dc(i);
}

return NULL;
}

int main() {

numCPU = sysconf(_SC_NPROCESSORS_ONLN);
pthread_t threads[numCPU];

for (int i = 0; i < numCPU; ++i)
pthread_create(&threads[i], NULL, *worker, (void *)i);

for (int i = 0; i < numCPU; ++i)
pthread_join(threads[i], NULL);

return 0;
}

It's not 1970 and memory doesn't cost an arm and a leg anymore.

Fucking idiot.

>>49

Apologies for my outburst.

>>49
He's not wrong

>>23,44
Why doesn't this work on my ODROID-XU4?

function runcount(int x){
i=0; j=0; k=0;
j=x & 0x01;
while(x >=1){
x = x>>1;
i++;
((x & 0x01) == j) || i=0;
if (i>k) k = i;
j = x & 0x01;
}
return k;
}

function gapcount(int x){
i=0; k=0; //j=0;

while(((x & 0x01) ==0) && (x>=1))
x = x>>1;

while(x >=1){
x = x>>1;
i++;
((x & 0x01) == 0) || i=0;
if (i>k) k = i;
}
return k;
}

Devil dubs