how to check if at least three of last four bits (LSB) are on

Question

I tried doing this in C:

    int val = 0xCAFE;
int uc = val & 14;


if (val & 15 == 15 || val & 7 == 7 || val & 11 == 11|| val & 13 == 13 || val & 14 == 14){
    printf("asdjfkadscjas \n");
}

However this is not printing the random string as it should. It worked for 15,7,11,13 tho.

If anyone knows of a better way that would be helpful. I am bad with bitwise operator.

Thanks

Answer 1

Psuedocode:

int set = 0;
for(i = 0 to 3)
    set++ if val & (1<<i)
if(set >= 3)
    ...

Answer 2

count  =  (val >> 1) & 1 + (val >> 2)&1 + (val >> 3)&1 + (val&1)

or

count  =  precalculated_counts[val & 0x0F];

Answer 3

You're having an operator precedence problem, not an operation problem. == is of higher precedence than &:

if ((val & 15) == 15 || (val & 7) == 7 || ...

Also, you don't need to check for 15.

Answer 4

The comparison operator has precedence to the bitwise and operator, so put parens around the & operator:

if( (val & 15) == 15 || (val & 14) == 14 || ... ) {
    printf( "random string...\n" );
}

Answer 5

unsigned nNumOfBitEnabled=0;
    for(unsigned nBit=0; nBit<4; ++nBit)
    {
        // Check bit state
        if ((val >> nBit) & 0x1)
        {
            ++nNumOfBitEnabled;
        }
    }

Answer 6

A simple way to do this, which also shows your intent clearly, would be:

if (!!(val & 0x01) + !!(val & 0x02) + !!(val & 0x04) + !!(val & 0x08) >= 3)

Answer 7

if (((value & 1 ? 1 : 0) +
     (value & 2 ? 1 : 0) +
     (value & 4 ? 1 : 0) +
     (value & 8 ? 1 : 0)) >=3)

Answer 8

Alternative solution: You can put all your numbers into a binary-coded lookup table:

int AtleastThreeBits (int a)
{
  return (0xe880>>(a&15))&1;
}

Each bit of the magic number represents an answer. In the constant 0xe880 bits 7,11,13,14 and 15 are set. You select the correct bit using a shift and mask it out.

It's not as readable as your solution but faster..

Answer 9

You could try a look-up table! Then you could change your threshold easily.

static int nibbleCounts[] = { 0, 1, 1, 2,
                              1, 2, 2, 3,
                              1, 2, 2, 3,
                              2, 3, 3, 4 };
if (nibbleCounts[value & 0xF] >= 3)
    puts ("Hello!");

Answer 10

You can use the carry from an addition to "fill in" the 1st 0-bit "hole" in a number. We allow at most one of these in the bottom nibble, so combining the original value and the "filled-in" version with | will produce a bottom nibble with all 1-bits in this case:

if (((val | (val + 1)) & 15) == 15)

I think this has the fewest operations of any (lookup-table-free) solution so far -- no, actually Nils Pipenbrinck's clever "in-place lookup table" has even fewer!

Answer 11

int x = val & 0x0f;    // mask to keep only the interesting bits

switch (x) {
    case  7:  // 0b0111 ==  7
    case 11:  // 0b1011 == 11
    case 13:  // 0b1101 == 13
    case 14:  // 0b1110 == 14
    case 15:  // 0b1111 == 15
        // at least 3 bits are set
        // do whatever you need, like

        printf("asdjfkadscjas \n");
        break;
}

It's not particularly clever, but I think the next pinhead that comes along and looks at the code will have no problem figuring out what the intent is and whether or not it's correct. And that's a really big plus when that pinhead is me trying to figure out what the hell I did in that function last week.

Answer 12

Interesting tangent to this question - I think I know a sort of clever answer to the question "How many bits are set in this value"

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

uint8_t NumBitsSet(uint32_t value){
   uint8_t num_bits_set = 0;
   while(value != 0){
     value = value & (value-1);
     num_bits_set++;
   }

   return num_bits_set;
}

int main(int argc, char *argv[]){
  uint32_t value = 2147483648;
  printf("numbits set in %x = %d", value, NumBitsSet(value));
  return 0;
}

You can use this as a basis for determining if exactly one bit is set, though you have to make a special check for zero.

uint8_t exactly_one_bit_set = (value & (value-1)) == 0 ? 1 : 0;

The trick here is that if a value has one bit set then one less than that value will have all the bits below that bit set and that bit cleared. and-ing those two things together will be always be zero.