Is there a trick to testing if a non-specific bit is set anywhere in an int?

Question

I want to test whether any single bit is set in a C int. I don't care which bit it is.

Equivalent to

if (1 == count_bits (n))

I'm curious if there is a non-looping algorithm for this which does not require special hardware support.

Your text might indicate, that you are looking for `a == 0`, but your code snippet indicates, that you want to check if *exactly one* bit is set. Can you please specify it? — hellow, Oct 29 '18 at 10:19

H.cohen · Answer 1 · 2018-10-29T10:40:40.560

5

If only one bit is set, then the number is a power of two.

unsigned int IsPowerOfTwoNoLoop(unsigned int input)
{
    unsigned int temp = input;
    if(0 == input)
    {
      return 0;
    }
    temp -= 1;
    /*Example of the logic:*/
    /*  0100 (4 DEC) - 1 = 0011
        0011 & 0100 = 0000 
    */
    if (temp & input) /* if not zero - not pow of two */
    {
        printf("%u Is NOT the power of two !\n", input);
        return 0;
    }

    printf("%u Is the power of two !\n", input);
    return 1;
}

edited Oct 29 '18 at 10:40

answered Oct 29 '18 at 10:22

H.cohen

517
3
9

For the explanation see https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2#600306 – hellow Oct 29 '18 at 10:26
I would suggest to use `uint32_t` instead of `unsigned int`. Why don't you accept any digit and reinterpret them as an unsigned value in your function? – hellow Oct 29 '18 at 10:33
1

Review: it would be much clearer (=better) to return `bool` from this function. – unwind Oct 29 '18 at 10:41

Toby Speight · Answer 2 · 2018-10-29T11:30:38.820

1

The simplest way is probably to convert to an unsigned type.

Then we are simply testing whether we have an exact power of two.

We can use a simple observation that these are the only non-zero numbers that have no bits in common with n-1:

bool is_power_of_two(unsigned int n)
{
    return n && ! (n & (n-1));
}

edited Oct 29 '18 at 11:30

answered Oct 29 '18 at 10:40

Toby Speight

27,591
48
66
103

"This code falsely returns one when input is zero. – Eric Postpischil" – Kami Kaze Oct 29 '18 at 10:47
Oops - I mistakenly thought I'd taken that into account, and failed. – Toby Speight Oct 29 '18 at 11:30

Is there a trick to testing if a non-specific bit is set anywhere in an int?

2 Answers2