Counting consecutive 1's in C

Question

Possible Duplicate:
Finding consecutive bit string of 1 or 0

Is it possible to count, from left, consecutive 1's in an integer? So: total number of consecutive set bits starting from the top bit.

Using only:

! ~ & ^ | + << >>

-1= 0xFFFFFFFF would return 32

0xFFF0F0F0 would return 12 (FFF = 111111111111)

No loops, unfortunately.

Can assume the machine:

1. Uses 2s complement, 32-bit representations of integers.

2. Performs right shifts arithmetically.

3. Has unpredictable behavior when shifting an integer by more than the word size.

I'm forbidden to:

1. Use any control constructs such as if, do, while, for, switch, etc.

2. Define or use any macros.

3. Define any additional functions in this file.

4. Call any functions.

5. Use any other operations, such as &&, ||, -, or ?:

6. Use any form of casting.

7. Use any data type other than int. This implies that you cannot use arrays, structs, or unions.

I've looked at Finding consecutive bit string of 1 or 0 It's using loops, which I can't use. I don't even know where to start.

(Yes, this is an assignment, but I'm simply asking those of you skilled enough for help. I've done pretty much all of those I need to do, but this one just won't work.)

(For those downvoting simply because it's for school: FAQ: 1 a specific programming problem, check 2 However, if your motivation is “I would like others to explain ______ to me”, then you are probably OK.)

Answer 1

You can do it like this:

int result = clz(~x);

i.e. invert all the bits and then count leading zeroes.

clz returns the number of leading zero bits (also commonly known as ffs or nlz) - see here for implementation details: http://en.wikipedia.org/wiki/Find_first_set#Algorithms

Answer 2

Here you are. The function argument may be signed or unsigned. The alg is independent on signedness.

int leftmost_ones(int x)
{
    x = ~x;
    x = x | x >> 1 | x >> 2 | x >> 3 | x >> 4 | x >> 5 | x >> 6 | x >> 7 | 
        x >> 8 | x >> 9 | x >> 10 | x >> 11 | x >> 12 | x >> 13 | x >> 14 | 
        x >> 15 | x >> 16 | x >> 17 | x >> 18 | x >> 19 | x >> 20 | x >> 21 | 
        x >> 22 | x >> 23 | x >> 24 | x >> 25 | x >> 26 | x >> 27 | x >> 28 | 
        x >> 29 | x >> 30 | x >> 31;
    x = ~x;
    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}

A version with some optimization:

int leftmost_ones(int x)
{
    x = ~x;
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    x = ~x;

    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}

Answer 3

Can you use a loop?

int mask = 0x80000000;
int count = 0;
while (number & mask) {
    count += 1;
    mask >>= 1;
}

Answer 4

I think it's doable, by basically unrolling the typical loop and being generally annoying.

How about this: an expression that is 1 if and only if the answer is 1? I offer:

const int ok1 = !((number & 0xc0000000) - 0x800000000);

The ! and subtraction are to work around that someone broke the == key on our keyboard, of course.

And then, an expression that is 1 if and only if the anwer is 2:

const int ok2 = !((number & 0xe0000000) - 0xc0000000);

If you continue to form these, the final answer is their sum:

const int answer = ok1 + ok2 + ... + ok32;

By the way, I can't seem to remember being given these weirdly restricted assignments when I was in school, I guess times have changed. :)

Answer 5

int count_consecutive_bits(unsigned int x) {
    int res = 0;
    while (x & 0x80000000) { ++res; x <<= 1; }
    return res;
}