# Is Hamming weight written in binary operations only?

I need to write an expression of one Hamming byte weight only on binary operations (&, ^, →); without any loop, just formulas.

I know there are many algorithms that allow you to calculate Hamming weights, but they all use arithmetic operations or a loop.

If we take the 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 the next two sums are more complex.

Does anyone have a hint?

UPDATE: Thank you for your help. I actually needed something like the 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 the Hamming weight of the variable. It does not contain any +, - or comparison instructions and can run on 8-bit microcontrollers. However, it requires more operations than most other solutions. Now I am trying to simplify it.

UPDATE2: Another solution based on 64 bit registers suggested by @Evgeny Kluev

+3

source to share

I'm not sure if this is what you are looking 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, the change operation is used twice as a replacement for array indexing (to find 4-bit weights). And another switch operation uses array indexing to perform the addition.

+3

source

I think the best you can do is O (log n). Here is the code (in Go) for a pop-count of a 32 bit integer. Expanding this to 64-bit should be obvious if you need it, hope the comments make it clear what's really 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)
}
```

```
+7

source

All Articles