How To Find The Leading Number Of Zero's In a Number using C

Question

for example,if i have number 64,then its binary representation would be 0000 0000 0000 0000 0000 0000 0100 0000 so leading number of zero's is 25. remember i have to calculate this in O(1) time.

please tell me the right way to do that.even if your complexity is >O(1) please do post your answer. thanx

Solution 1

See here for the 32-bit version and other great bit-twiddling hacks.

// this is like doing a sign-extension
// if original value was   0x00.01yyy..y
// then afterwards will be 0x00.01111111
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x |= (x >> 32);

and after that you just need to return 64 - numOnes(x). A simple way to do that is numOnes32(x) + numOnes32(x >> 32) where numOnes32 is defined as:

int numOnes32(unsigned int x) {
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}

I haven't tried out this code, but this should do numOnes64 directly (in less time):

int numOnes64(unsigned long int x) {
     x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L);
     x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L);
     // collapse:
     unsigned int v = (unsigned int) ((x >>> 32) + x);
     v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f);
     v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff);
     return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff);
}

Solution 2

Right shift is your friend.

    int input = 64;
    int sample = ( input < 0 ) ? 0 : input;
    int leadingZeros = ( input < 0 ) ? 0 : 32;

    while(sample) {
        sample >>= 1;
        --leadingZeros;
    }
    printf("Input = %d, leading zeroes = %d\n",input, leadingZeros);

Comments

[user609306]

thanx john ....i wanted the same thing.. but its big O is O(log n) base 2. if you take 64 then you have to move bits by log 64 times which is 6 times take some other number n for which while loop would run log n times

[kriss]

@user609306: as the largest possible n here is 32 (or 64 for 64 bits numbers) you should be very cautious using ceil. constants times behind call to ceil can be way larger than the time to perform 64 loops or lesser.

[MotiNK]

Branches in code for this kind of thing doesn't make sense. Using bit-twiddling techniques you can do this without any branches, see e.g., aggregate.org/MAGIC/#Leading Zero Count

[user3256556]

Actually, such branches do make sense on ARM type chips that have conditional execution and where each line of code will be replaced by 3 instructions (2 of them conditional) of the type: ANDS R4, R0, #0xff addeq R1, R1, #8, moveq R0, R0 shl 8. Then the whole function turns into 3*5 instruction with precise time execution. Bit twideling will probably not be any better. Of course, ARM chips have CLZ instructions that you can use!