Finding Bit Positions in an unsigned 32-bit integer

I think I might have been asleep in my CS class when they talked about Bit Positions, so I am hoping someone can lend a hand.

I have a unsigned 32-bit integer (Lets use the value: 28)

According to some documentation I am going over, the value of the integer contains flags specifying various things.

Bit positions within the flag are numbered from 1 (low-order) to 32 (high-order). All undefined flag bits are reserved and must be set to 0.

I have a Table that shows the meanings of the flags, with meaning for the numbers 1-10.

I am hoping that someone can try and explain to me what this all means and how to find the "flag" value开发者_StackOverflow中文版(s) from a number like, 28, based off of bit position.

Thanks

28 converts to 11100 in binary. That means bits 1 and 2 are not set and bits 3, 4 and 5 are set.

A few points: first, anybody who's really accustomed to C will usually start the numbering at 0, not 1. Second, you can test of individual flags with the bitwise and operator (&), as in:

#define flag1 1    //  1 = 00 0001
#define flag2 2    //  2 = 00 0010
#define flag3 4    //  4 = 00 0100
#define flag4 8    //  8 = 00 1000
#define flag5 16   // 16 = 01 0000
#define flag6 32   // 32 = 10 0000

if (myvalue & flag1)
    // flag1 was set

if (myvalue & flag4)
    // flag4 was set

and so on. You can also check which bits are set in a loop:

#include <stdio.h>

int main() { 
    int myvalue = 28;
    int i, iter;

    for (i=1, iter=1; i<256; i<<=1, iter++)
        if (myvalue & i)
            printf("Flag: %d set\n", iter);
    return 0;
}

should print:

Flag: 3 set
Flag: 4 set
Flag: 5 set

Instead of looping through every single bit, you can instead loop through only the set bits, which can be faster if you expect bits to be sparsely set:

Assume the bit field is in (scalar integer) variable field.

while (field){
  temp = field & -field;  //extract least significant bit on a 2s complement machine
  field ^= temp;  // toggle the bit off
  //now you could have a switch statement or bunch of conditionals to test temp
  //or get the index of the bit and index into a jump table, etc.
}

Works pretty well when the bit field is not limited to the size of a single data type, but could be of some arbitrary size. In that case, you can extract 32 (or whatever your register size is) bits at a time, test it against 0, and then move on to the next word.

To get an int with the value 0 or 1 representing just the nth bit from that integer, use:

int bitN = (value >> n) & 1;

But that's not usually what you want to do. A more common idiom is this:

int bitN = value & (1 << n);

In this case bitN will be 0 if the nth bit is not set, and non-zero in the case that the nth bit is set. (Specifically, it'll be whatever value comes out with just the nth bit set.)

Assuming flags is unsigned...

int flag_num = 1;
while (flags != 0)
{
    if ((flags&1) != 0)
    {
        printf("Flag %d set\n", flags);
    }
    flags >>= 1;
    flag_num += 1;
}

If flags is signed you should replace

flags >>= 1;

with

flags = (flags >> 1) & 0x7fffffff;

Use a log function, with base 2. In python, that would look like:

import math 

position = math.log(value, 2)

If position is not an integer, then more than 1 bit was set to 1.

A slight variation of @invaliddata's answer-

unsigned int tmp_bitmap = x;        
while (tmp_bitmap > 0) {
    int next_psn = __builtin_ffs(tmp_bitmap) - 1;
    tmp_bitmap &= (tmp_bitmap-1);
    printf("Flag: %d set\n", next_psn);
}

// You can check the bit set positions of 32 bit integer.
// That's why the check is added "i != 0 && i <= val" to iterate till 
// the end bit position.
    void find_bit_pos(unsigned int val) {
            unsigned int i;
            int bit_pos;
            printf("%u::\n", val);
            for(i = 1, bit_pos = 1; i != 0 && i <= val; i <<= 1, bit_pos++) { 
                    if(val & i)
                            printf("set bit pos: %d\n", bit_pos);
            }
    }

Let's say that you have an array of integers, and you want to find all the positions (32-bit positions) where the bits are set collectively i.e. for a particular bit position how many set bits you will have in total by considering all the integers. In this case what you can do is that check for every Integer and mark its set bit position :

// let arr[n] is an array of integers of size n.
int fq[33] = {0} // frequency array that will contain frequency of set bits at a particular position as 1 based indexing.
for(int i=0; i<n; i++) {
   int x = arr[i];
   int pos = 1; // bit position
   for(int i=1; i<=pow(2,32); i= i<<1) {  // i is the bit mask for checking every position and will go till 2^32 because x is an integer.
      if(x & i) fq[pos]++;
      pos++;
   }
}