Finding Bit Positions in an unsigned 32-bit integer

Question

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(s) from a number like, 28, based off of bit position.

Thanks

Answer 1

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

Answer 2

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;

Answer 3

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.)

Answer 4

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.

Answer 5

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.

Answer 6

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);
}

Answer 7

// 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);
            }
    }

Answer 8

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++;
   }
}

Answer 9

An MSVC variation of @boolAeon's answer

#include <vector>
#include <intrin.h>

std::vector<unsigned long> poppos(const unsigned long input)
{
    std::vector<unsigned long> result;
    result.reserve(sizeof(input) * CHAR_BIT);

    unsigned long num = input;
    unsigned long index = -1;

    while (_BitScanForward(&index, num))
    {
        result.push_back(index);
        num &= num - 1;
    }

    return result;
}

Answer 10

I know this is a old post, but this may come in handy for someone. I assume you are working with embedded systems. If you are working with ARM architecture, you may benefit from the __CLZ instruction - "Count leading zeros". See the documentation of STM32F103C8T6:

/**
  \brief   Count leading zeros
  \details Counts the number of leading zeros of a data value.
  \param [in]  value  Value to count the leading zeros
  \return             number of leading zeros in value
 */
#define __CLZ             (uint8_t)__builtin_clz

I tested the following:

uint32_t data = 0b00000000000000000000000000000001;
uint8_t count = __CLZ(data);

which makes count to be 31.

I also tested the following:

uint32_t data = 0b10000000000000000000000000000000;
uint8_t count = __CLZ(data);

which makes count to be 0.

So,

uint8_t count = 31 - __CLZ(data);

may solve your problem with minimal footprint and clock cycles.