I need to write an expression of one byte Hamming weight in terms of binary operations only (&, ^, >>); without any loop, just a formula.
I know that there are plenty algorithms, that allow computing Hamming weight, but all of them use arithmetical operations or looping.
If we take an algorithm from http://en.wikipedia.org/wiki/Hamming_weight, then the first sum D=B+C can be written as D = B^C^(B&C << 1), but two following sums are more complicated.
Does anyone have a hint?
UPDATE: Thank you for help guys. Actually, I needed something like following:
int popcount_1(unsigned char in){
unsigned char m1 = 0x55;
unsigned char m2 = 0x33;
unsigned char m4 = 0x0f;
unsigned char B,C = 0;
unsigned char x = in;
x = (x & (x << 1) & (m1 << 1)) | (m1 & (x ^ (x >> 1)));
B = x & m2;
C = (x >> 2) & m2;
x = B ^ C ^ ((B & C) << 1);
B = (x & m4 ) ^ ((x >> 4) & m4);
C = (x & ((x >> 4) & m4)) << 1;
x = B ^ C ^ ((B & C) << 1);
return x;
}
This code will result in Hamming weight of variable in. It does not contain any +, -, or comparison instructions and it can work on 8bits microcontrollers. Nevertheless, it takes more operations than most of other solutions. Now, I am trying to simplify it.
UPDATE2: Another solution, based on 64 bits registers, is proposed by @Evgeny Kluev
I think the best you can do is O(log n). Here is code (in Go) for the pop-count of a 32-bit integer. Extending this to 64-bits should be obvious if you need it, hopefully the comments make it clear what is actually going on:
func popCount(n uint32) int {
// each bit in n is a one-bit integer that indicates how many bits are set
// in that bit.
n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555)
// Now every two bits are a two bit integer that indicate how many bits were
// set in those two bits in the original number
n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333)
// Now we're at 4 bits
n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F)
// 8 bits
n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF)
// 16 bits
n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF)
// kaboom - 32 bits
return int(n)
}
I'm not sure if this is what you search for, but here is just a formula using only shifts and bitwise and:
int weight(unsigned char x)
{
return ((0x876543210 >>
(((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >>
((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2))
& 0xf;
}
Here shift operation is twice used as a substitute for array indexing (to find 4-bit hamming weights). And one more shift operation uses array indexing to perform addition.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With