Vertical bitwise COUNT (sum of units in the same position)

Question

Is there an efficient way to execute COUNT for the same positions in many variables? The count function must fill the array with the sum of the numbers in the corresponding bit number. For example, we have the following three variables (I use 8-bit variables to make them simple):

uint8_t a = 0xF; // 0000 1111 uint8_t b = 0x3C; // 0011 1100 uint8_t c = 0xF0; // 1111 0000 int result[8]; // some operations ... count << result[0] << result[1] << .... // prints 1122 2211 

I found many solutions to summarize them in the whole single variable, but not for the indicated problem.

Answer 1

This little code does exactly what you want. You can easily expand it to support N variables through a small search array. Note the use of double operation. It should drag the output to 0 or 1.

 #include <iostream> using namespace std; int main() { uint8_t a = 0xF; // 0000 1111 uint8_t b = 0x3C; // 0011 1100 uint8_t c = 0xF0; // 1111 0000 unsigned result[8]; for(int i = 0; i < 8; ++i) { unsigned mask = 1 << i; result[i] = !!(a & mask) + !!(b & mask) + !!(c & mask); } for(int i = 0; i < 8; ++i) cout << result[i]; } 

Answer 2

Expand each binary digit uint8_t into the hexadecimal digit uint32_t and add them. Well, if not more than 15 per bit.

 #include <stdio.h> #include <stdint.h> // See below for tighter code uint32_t shift_nibble(uint8_t x) { uint32_t y = 0; uint32_t mask = 1; while (x) { if (x & 1) { y |= mask; } mask <<= 4; x >>= 1; } return y; } void PrintVerticalBitwiseCount(const uint8_t *x, size_t size) { uint32_t y = 0; for (size_t i=0; i<size; i++) { y += shift_nibble(x[i]); } printf("%08lX\n", (unsigned long) y); } int main(void) { const uint8_t a[] = { 0xF, 0x3C, 0xF0 }; PrintVerticalBitwiseCount(a, sizeof a/sizeof *a); return 0; } 

Output

 11222211 

---

The candidate is faster than shift_nibble() . Put on your octal hat

 uint32_t shift_nibble(uint8_t x) { uint32_t y; y = UINT32_C(0x01010101) & (UINT32_C(0001010101) * (x & 0x55)); y |= UINT32_C(0x10101010) & (UINT32_C(0010101010) * (x & 0xAA)); return y; } 

Answer 3

As a template, I propose a function below in C ++ 11. The returned list has a bit in the corresponding place for each bit, that is, the least significant number of bits is at position 0, the next at position 1, etc. Hope this helps someone.

 template<typename T> std::list<long> vertical_bit_sum(std::vector<T> items) { size_t bits = sizeof(T) * 8; std::list<long> result; do { long count = 0; for ( T item : items) { count += (0x1 & (item >> (bits-1))); } result.push_front (count); --bits; } while( bits > 0); return result; } std::list<long> result= vertical_bit_sum<uint8_t>( { 0xF, 0x3C, 0xF0 }); 

Answer 4

Do something like this:

 uint64_t accum = 0; uint64_t table[0x100] = {.. precomputed vals ...}; int count = 0xFF; while(bytes_available()) { if(--count == 0) { count = 0xFF; for(int i = 0; i < 8; i++) result[i] = ((uint8_t*)&accum)[i]; accum = 0; } accum += table[(uint8_t)get_next_byte()]; } 

Answer 5

For maximum speed, you can process 8 samples in parallel, storing 8 bytes packed in one 64-bit battery.

Initialize a lookup table with 256 64-bit entries, which are the original 8 bits extended to bytes. (For example, the entry Lookup[0x17u] mapped to 0x0000000100010101ul .)

Counting is done only with

 Acc+= Lookup[Byte]; 

You extract individual counters by matching an array of 8 bytes on 64 bits.

You can accumulate 256 times before overflowing; if you need more, accumulate in blocks of 256, and after the block has been processed, transfer the calculations to larger batteries.

If you need to accumulate no more than 16 times, 32-bit batteries are enough.

Answer 6

Determining if 1 is in a certain position in a variable is much simpler than ordinary population calculations.

 bool hasOneAtPosition(int position, int target) { int mask = 1 << position; return (target & mask) != 0; } 

... Just name it on all of your inputs and increment the counter every time it returns true. Simplez.