Geek asks and answers

Count consecutive 1 in C

Possible duplicate:
Search for a serial bit string 1 or 0

Is it possible to count to the left of sequential 1 as an integer? So: the total number of consecutive bits, starting with the top bit.

Use only:

! ~ & ^ | + << >>

-1= 0xFFFFFFFFwill return 32

0xFFF0F0F0 will return 12 (FFF = 111111111111)

Unfortunately no cycles.

You can consider the car:

  • Uses 2s padding, 32-bit integer representations.

  • Performs the correct shifts arithmetically.

  • It has unpredictable behavior when shifting an integer greater than the size of a word.

I am forbidden to:

  • Use any control constructors such as if, do, while, for, switch, etc.

  • Define or use any macros.

  • Define any additional functions in this file.

  • Call any functions.

  • , & &, ||, - ?:

  • .

  • , int. ,   , .

1 0 , . , .

(, , , . , , .)

( , , : -: 1 , 2 , " , ______", , , .)

+5
5

. . .

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

:

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);
}
+2

?

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

:

int result = clz(~x);

. .

clz ( ffs nlz) - . : http://en.wikipedia.org/wiki/Find_first_set#Algorithms

+1

I think this is doable, basically unfolding a typical cycle and being generally annoying.

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

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

!and subtraction should work for someone to break the key ==on our keyboard, of course.

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

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

If you continue to form them, the final answer will be their sum:

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

By the way, I can’t remember that I was given these strangely limited tasks when I was in school, I think the times have changed. :)

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

More articles:


All Articles