cppdevelopment

Counting transitions in a bit string

We need to count a number of transitions in a bit string from 0->1 and 1->0. I needed this in order to determine Uniform Descriptor in Local Binary Patterns(LBP)

Samples

0000 0000  (0 Transitions : Uniform)    0x0
1110 0011  (2 Transitions : Uniform)    0xE3
0101 0000  (4 Transitions : NonUniform) 0x50
0000 1010  (4 Transitions : NonUniform) 0xA
0000 1001  (3 Transitions : NonUniform) 0x9

Sample run (0xE3)

0x      e3 :      227 :: 00000000000000000000000011100011
0x      71 :      113 :: 00000000000000000000000001110001
0x      92 :      146 :: 00000000000000000000000010010010
Transition : 3

Implemenation

We are going to shift the value to the right and then XOR it with the original value to get the number of transitions. From there we going to use population count to get the count of the on bits.

XOR Truth table

INPUT	         OUTPUT
-----------------------
A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0
 
template <class T> void bitstr(const T& out) noexcept;
template <class T> int  popcnt(const T& val) noexcept;
 
int main()
{
    // Uniform descriptors
    // 0000 0000  (0 Transitions : Uniform)    0x0
    // 1110 0011  (2 Transitions : Uniform)    0xE3
    // 0101 0000  (4 Transitions : NonUniform) 0x50
    // 0000 1010  (4 Transitions : NonUniform) 0xA
    // 0000 1001  (3 Transitions : NonUniform) 0x9
 
    int a = 0xE3;
    int b = a >> 1;
    int c = a ^ b;
    int count = popcnt(c);
 
    bitstr(a);
    bitstr(b);
    bitstr(c);
 
    std::cout << "Transition : " <<count;
 
    return 0;
}
 
 
template <class T>
int popcnt(const T& val) noexcept
{
    int bitcount;
    __asm__ ("popcnt %1, %1" : "=r" (bitcount) : "0" (val));
    return bitcount;
}
 
template <class T>
void bitstr(const T& out) noexcept
{
    std::bitset<CHAR_BIT * sizeof(T)> bs(out);
    auto val =  static_cast<int>(out);
    std::cout << "0x"
              << std::setw(8) << std::hex << val << " : "
              << std::setw(8) << std::dec << val<< " :: " << bs << std::endl;
}

Gist

Leave a Reply

Your email address will not be published. Required fields are marked *