Search code examples
c++binarybit-manipulationpowerset

how to use bit representation to access indexable data structure

Given an indexable data structure, say vector = ['a','b','c'] of size n=3 and an int i = 3, I would like to transform the 3 into its n-bit binary representation (011) and return the elements ['b','c'] of the vector. That is, for each 1 in the binary representation, return the element at that location. But how do I talk about 'location' in a binary number? I'm having trouble mapping one idea to the other. Any help appreciated.

Solution

  • Use bit shifting to test every bit of i:

     for(x=0; x<sizeof(int) * 8; x++)
 {
     if((i & (1<<x)) > 0)
     {
        // bit at position x is set in i
        add vector[i];          
     }
 }

    this will result in

    011 & 001  = 001 // true
011 & 010 =  010 // true
011 & 100 =  000 // false
.. etc