Count the number of contiguous 1 bits from the left

Question

I am stuck on this problem: Assume that we have 32-bit integer, write a C function to count the number of contiguous 1 bits, from the left. For example:

leftCount(0xFF000000) = 8
leftCount(0x0FFFFFFF) = 0 (because the number starts with 0)
leftCount(-1) = 32

In the function, I am allowed to use logical operators such as ! ~ & ^ | + << >>

No loop and condition structure is allowed.

Thanks

Note that only `!` is a logical operator (of those you listed). — jrok, Sep 08 '12 at 11:31
Btw, does it really matter if we count starting from the left or right? — , Sep 08 '12 at 11:32
@H2CO3 It does matter: `11101111`, the correct result for OP is 3, not 4. — jrok, Sep 08 '12 at 11:35
What is the question? So just start counting them. What exactly do you need help with? — David Schwartz, Sep 08 '12 at 11:51
Are you allowed to use loops …? May you use temporary variables …? — Kijewski, Sep 08 '12 at 11:57

score 6 · Answer 1 · answered Sep 08 '12 at 11:33

You can test if bit x is set in value y by evaluating y & (1 << x). It is zero if the bit is not set.

Using this, you can just loop from 31 down to 0, checking if each bit is set, stopping when your reach an unset bit. You should be able to code this yourself.

You can speed this up by binary searching. You can check if the first 16 bits are set by evaluating (y & 0xFFFF0000) == 0xFFFF0000. If it is, then you can check the next 8 bits in a similar manner; and if it is not, then you can check the first 8 bits. Recurse down using this method and you'll have a faster algorithm.

score 6 · Answer 2 · edited Jun 20 '20 at 09:12

6

In GCC you can use a built-in function:

Built-in Function: int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

You have to negate the input using binary negation: ~x (0 will become 1, and vice versa).

Here is a more academic solution:

#include <stdio.h>
#include <stdint.h>

int leftCount (unsigned int value) {
    if (~value == 0) {
        return 32; // you said your ints were 32 bits, so the code assumes that
    }
    int result = 0;
    while (value >> 31 == 1) { // test if highest bit is set
        value <<= 1; // shift the input to the left
        ++result; // one more bit was seen
    }
    return result;
}

int main (void) {
    unsigned int value;
    while (scanf ("%i", &value) == 1) {
        printf ("leftCount(0x%x) == %u\n", value, leftCount(value));
    }
    return 0;
}

edited Jun 20 '20 at 09:12

Community

1
1

answered Sep 08 '12 at 11:39

Kijewski

25,517
12
101
143

Useful answer, but not so much for the OP. This is a homework question... – jrok Sep 08 '12 at 11:46
@jrok Oh, I didn't see that. I'll think about a better solution for OP's case. – Kijewski Sep 08 '12 at 11:49
It still is hardware and compiler specific. Not all machines have primitive instructions for counting populated bits. Does GCC supply this function on these platforms, too? – wildplasser Sep 08 '12 at 11:51
@wildplasser it is compiler specific (but clang knows it, too). It is not platform specific. GCC will know an optimized asm code for this function for every target platform it supports. – Kijewski Sep 08 '12 at 11:54
In that case, it still is compiler-specific. Does GCC supply a drop-in replacement for architectures that don't have bitcount instructions? (I suppose there are supported microcontrollers that don't have popcount instructions). Also C was intended to be portable. GCC != C. – wildplasser Sep 08 '12 at 12:00
@wildplasser why is bitcount involved in this? That's just one way to implement clz - and not a particularly good one on many platforms. – harold Sep 08 '12 at 13:09
@harold: I intended to use a vague/general term for the whole family of {ffs/clz} -like instructions. Any of them may or may not be available on a particular platform. – wildplasser Sep 08 '12 at 17:35

score 3 · Answer 3 · answered Sep 08 '12 at 11:40

3

There is a fast function to count the number of leading zeros, and it's easy to transform this problem to that: complement the input.

int leftCount = input == 0 ? 0 : __builtin_clz(~input);

There's not even an algorithm there.

answered Sep 08 '12 at 11:40

harold

61,398
6
86
164

Finally something meaningful... +1. – Sep 08 '12 at 11:41
@H2CO3 well to be fair, I was beaten by a minute by Kay.. guess I should type faster :) – harold Sep 08 '12 at 11:42
I did upvote his answer as well. – Sep 08 '12 at 11:42
+1, and to be fair: this is a previous answer of me: http://stackoverflow.com/a/11376759/416224. – Kijewski Sep 08 '12 at 11:46
I wonder not consider this to meet the requirement to "write a C function". – David Schwartz Sep 08 '12 at 12:07
@DavidSchwartz no indeed, it's not a function. – harold Sep 08 '12 at 13:01

score 1 · Answer 4 · answered Sep 08 '12 at 16:44

I found myself a solution on the Internet. But my requirement is to use not more than 50 logical operators, so anybody help me optimize this function, please.

int bit_count_from_left(int x) {
/* Shift every bit to the rightmost bit and & it with 1, then start from the leftmost bit and determine 
 * whether a given bit and all the bits to its left are set to 1. */
    int lb01 = ((x >> 31) & 1); int lb02 = ((x >> 30) & 1); int lb03 = ((x >> 29) & 1);
    int lb04 = ((x >> 28) & 1); int lb05 = ((x >> 27) & 1); int lb06 = ((x >> 26) & 1);
    int lb07 = ((x >> 25) & 1); int lb08 = ((x >> 24) & 1); int lb09 = ((x >> 23) & 1);
    int lb10 = ((x >> 22) & 1); int lb11 = ((x >> 21) & 1); int lb12 = ((x >> 20) & 1);
    int lb13 = ((x >> 19) & 1); int lb14 = ((x >> 18) & 1); int lb15 = ((x >> 17) & 1);
    int lb16 = ((x >> 16) & 1); int lb17 = ((x >> 15) & 1); int lb18 = ((x >> 14) & 1);
    int lb19 = ((x >> 13) & 1); int lb20 = ((x >> 12) & 1); int lb21 = ((x >> 11) & 1);
    int lb22 = ((x >> 10) & 1); int lb23 = ((x >> 9) & 1);  int lb24 = ((x >> 8) & 1);
    int lb25 = ((x >> 7) & 1);  int lb26 = ((x >> 6) & 1);  int lb27 = ((x >> 5) & 1);
    int lb28 = ((x >> 4) & 1);  int lb29 = ((x >> 3) & 1);  int lb30 = ((x >> 2) & 1);
    int lb31 = ((x >> 1) & 1);  int lb32 = ((x) & 1);
    int bool01 = lb01;          int bool02 = bool01 & lb02; int bool03 = bool02 & lb03;
    int bool04 = bool03 & lb04; int bool05 = bool04 & lb05; int bool06 = bool05 & lb06;
    int bool07 = bool06 & lb07; int bool08 = bool07 & lb08; int bool09 = bool08 & lb09;
    int bool10 = bool09 & lb10; int bool11 = bool10 & lb11; int bool12 = bool11 & lb12;
    int bool13 = bool12 & lb13; int bool14 = bool13 & lb14; int bool15 = bool14 & lb15;
    int bool16 = bool15 & lb16; int bool17 = bool16 & lb17; int bool18 = bool17 & lb18;
    int bool19 = bool18 & lb19; int bool20 = bool19 & lb20; int bool21 = bool20 & lb21;
    int bool22 = bool21 & lb22; int bool23 = bool22 & lb23; int bool24 = bool23 & lb24;
    int bool25 = bool24 & lb25; int bool26 = bool25 & lb26; int bool27 = bool26 & lb27;
    int bool28 = bool27 & lb28; int bool29 = bool28 & lb29; int bool30 = bool29 & lb30;
    int bool31 = bool30 & lb31; int bool32 = bool31 & lb32;
    int result = bool01 + bool02 + bool03 + bool04 + bool05 + bool06 + bool07 + bool08 + bool09 + bool10
        + bool11 + bool12 + bool13 + bool14 + bool15 + bool16 + bool17 + bool18 + bool19 + bool20
        + bool21 + bool22 + bool23 + bool24 + bool25 + bool26 + bool27 + bool28 + bool29 + bool30
        + bool31 + bool32;
    return result;
}

score 0 · Answer 5 · answered Sep 08 '12 at 12:11

Spoiler:

#include <limits.h>
#include <stdint.h>
#include <stdio.h>

unsigned naive_leading1bit_count(uint32_t val)
{
unsigned cnt;

for (cnt=0; val & (1u << (sizeof val*CHAR_BIT-1)); val <<=1 ) {
        cnt += 1;
        }
return cnt;
}

int main(void)
{
unsigned res;
uint32_t uuu;

for (uuu = 0xf; uuu; uuu <<=1) {
        res = naive_leading1bit_count( uuu );
        printf("%x: %u\n", uuu, res);
        }

return 0;
}

Count the number of contiguous 1 bits from the left

5 Answers5