0

I'm trying to check the number of set bits is 2 or more in negation of number. I'm trying to do that with checking if number is power of 2. But it's not working with negation of number. This is my code:

unsigned long int x = ~x; //x is given number
if(!(x & (x - 1))) printf("it have only one set bit);

Do you have any sugestion?

Tomasz
  • 191
  • 2
  • 12
  • Didn't really get what you need. If it is to count bits, have a look at this answer: http://stackoverflow.com/a/21863332/2002198 – Felipe Lavratti Dec 05 '16 at 00:09
  • I only want to check binary negation of given number has got 1 or (2 and more) set bits. I not need to know exact number of set bits. – Tomasz Dec 05 '16 at 00:14
  • You know how to test if a number has 1 bit set. Any non-zero number that doesn't have 1 bit set has at least 2 bits set. – Paul Hankin Dec 05 '16 at 00:21
  • What does "not working" mean and do you have a specific failing test case? – harold Dec 05 '16 at 00:32
  • I loop through positive (from 1 to 75kk) int and check it and my program return all of it have 2 or more set bits. – Tomasz Dec 05 '16 at 00:35
  • I am not sure but i think problem is that bit negation of int give negative int – Tomasz Dec 05 '16 at 00:42
  • The smallest 32bit number whose complement does *not* have at least 2 bits set is 0x7fffffff, so checking up to 75M is not enough – harold Dec 05 '16 at 00:43
  • Possible duplicate of [Query about working out whether number is a power of 2](http://stackoverflow.com/questions/666647/query-about-working-out-whether-number-is-a-power-of-2) – anatolyg Dec 12 '16 at 16:02

1 Answers1

0

One of the best solutions for finding the number of set bits (the population) in an unsigned integer representation of a number is with the Stanford Bit Twiddling Hack:

/* get number of 1's in binary number (population - pop) */
int getn1s (unsigned v) {
    v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
    return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

It has been published in a number of variations, and there is a general form available for up to 128-bit numbers as well.

David C. Rankin
  • 81,885
  • 6
  • 58
  • 85
  • If I understood correctly, OP does not want population count. See the comment "_I only want to check binary negation of given number has got 1 or (2 and more) set bits. I not need to know exact number of set bits._" – AlexD Dec 05 '16 at 02:57