CODEWITHSUNDEEP
c++calgorithmbit-manipulation
nosbor
nosbor

Reputation: 3009

Vertical bitwise COUNT (sum of ones on the same position)

Is there any efficient way to do COUNT of ones on the same position in many variables? The count function should fill array with sum of ones in corresponding bit number. For example we have following three variables (I use 8-bit variables to make it 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 for summing the ones in whole single variable, but not for the above problem.

Upvotes: 5

Views: 576

Answers (6)

user1196549
user1196549

Reputation:

For sheer speed, you can process 8 counts in parallel by keeping 8 bytes packed in a single 64 bits accumulator.

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

Counting is just performed with

Acc+= Lookup[Byte];

You retrieve the individual counters by mapping an array of 8 bytes on the 64 bits.

You can perform the accumulation 256 times before overflow occurs; if you need more, accumulate in blocks of 256, and after a block has been processed, transfer the counts to larger accumulators.

If you need to accumulate no more than 16 times, 32 bit accumulators will suffice.

Upvotes: 0

olegarch
olegarch

Reputation: 3891

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

Upvotes: 0

chux
chux

Reputation: 154243

Expand each uint8_t binary digit into a uint32_t hex digit and "add them up". Good as long as 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

A candidate faster 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;
}

Upvotes: 2

JimmyNJ
JimmyNJ

Reputation: 1194

As a template I suggest the function below in C++11. The returned list has the bit counts in the appropriate place for each bit, that is to say the least significant bit count is at position 0, the next most 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  });

Upvotes: 1

SenselessCoder
SenselessCoder

Reputation: 1159

This little code does exactly what you want. You can easily expand it to support N variables through a little lookup array. Notice the use of the double not operation. It is to drag the output to either be 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];
}

Upvotes: 2

Chris Kitching
Chris Kitching

Reputation: 2655

Determining if there's a 1 at a particular position in a variable is much simpler than doing a normal population count.

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

... Just call that on all your inputs and increment a counter every time it returns true. Simplez.

Upvotes: -1

Related Questions