5

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

Algorithmist
  • 6,657
  • 7
  • 35
  • 49
user609306
  • 1,333
  • 6
  • 17
  • 27
  • 4
    O(1) means that as you vary the problem, the time to compute the solution remains constant (roughly). That makes no sense with a fixed sized problem like yours. – sigfpe Jun 04 '11 at 03:42
  • 7
    Is this a homework question? What have you already tried? – Jacinda Jun 04 '11 at 03:46
  • 2
    I'm just now noticing the [functional-programming] tag -- is this _really_ [functional programming](http://en.wikipedia.org/wiki/Functional_programming) or do you just need a function that does this? – sarnold Jun 04 '11 at 04:01
  • You can put arbitrarily many 0s in front of any number in any base without changing it. Are you assuming a 32-bit integer type? If so, then say so. Please be aware that C is not required to provide a type with exactly 32 bits at all: the sizes of `char`/`short`/`int`/`long` are specified only as minimums and relative to each other. – Karl Knechtel Jun 04 '11 at 05:25
  • @sigfpe: using O(1) is correct here if you consider the size of the problem to be the number of leading zeros in binary representation. Many algorithms to do this have complexities depending on the number of leading zeros in the actual number. – kriss Aug 09 '13 at 13:23

6 Answers6

3

I just found this problem at the top of the search results and this code:

int pop(unsigned x) {
    unsigned n;
    n = (x >> 1) & 033333333333;
    x = x - n;
    n = (n >> 1) & 033333333333;
    x = x - n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

int nlz(unsigned x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return pop(~x);
}

where pop counts 1 bits, is several times faster than the first (upvoted) answer.

I didn't notice, question was about 64 bits numbers, so here:

int nlz(unsigned long x) {
    unsigned long y;
    long n, c;
    n = 64;
    c = 32;
    do {
        y = x >> c;
        if (y != 0) {
            n = n - c;
            x = y;
        }
        c = c >> 1;
    } while (c != 0);
    return n - x;
}

is a 64 bits algorithm, again several times faster than the mentioned above.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
2

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);
}
MotiNK
  • 421
  • 2
  • 12
1

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);
Prince John Wesley
  • 62,492
  • 12
  • 87
  • 94
  • 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 – user609306 Jun 04 '11 at 08:21
  • @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. – kriss Aug 09 '13 at 13:26
0

I would go with:

unsigned long clz(unsigned long n) {
    unsigned long result = 0;
    unsigned long mask = 0;
    mask = ~mask;
    auto size = sizeof(n) * 8;
    auto shift = size / 2;
    mask >>= shift;
    while (shift >= 1) {
        if (n <= mask) {
            result += shift;
            n <<= shift;
        }
        shift /= 2;
        mask <<= shift;
    }
    return result;
}
Tomasz Gawel
  • 8,379
  • 4
  • 36
  • 61
-1

Using floating points is not the right answer....

Here is an algo that I use to count the TRAILING 0... change it for Leading... This algo is in O(1) (will always execute in ~ the same time, or even the same time on some CPU).

int clz(unsigned int i)
{
  int zeros;
  if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0;
  if ((i&0xff)==0) zeros+= 8, i>>= 8;
  if ((i&0xf)==0) zeros+= 4, i>>= 4;
  if ((i&0x3)==0) zeros+= 2, i>>= 2;
  if ((i&0x1)==0) zeros+= 1, i>>= 1;
  return zeroes+i;
}
user3256556
  • 153
  • 8
  • 1
    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., http://aggregate.org/MAGIC/#Leading Zero Count – MotiNK May 19 '15 at 13:40
  • 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! – user3256556 Jun 13 '18 at 05:05
-1

Because the logarithm base 2 roughly represents the number of bits required to represent a number, it might be useful in the answer:

irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor()
=> 25
irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor()
=> 25
irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor()
=> 25
irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor()
=> 24

Of course, one downside to using log(3) is that it is a floating-point routine; there are probably some supremely clever bit-tricks to find the number of leading zero bits in integers, but I can't think of one off the top of my head...

sarnold
  • 102,305
  • 22
  • 181
  • 238