Hamming weight written only in binary operations?

Question

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

Nop, it is not. I am doing it to derive an analytic expression to optimise a key search in differential power analysis attack, based on Hamming weight/distance. Actually, I have almost found this expression, so I will post it soon. — Roman, Mar 30 '12 at 15:49
I'm not sure I understand, if it's just for optimization neither of these two constraints should exist and you'd need "whatever way is the fastest" (which is heavily platform-dependent) — harold, Mar 30 '12 at 17:40
The fastest byte-sized popcount on x86, assuming the bytes are in contiguous memory, is with a `pshufb` trick: http://wm.ite.pl/articles/sse-popcount.html — harold, Mar 30 '12 at 20:40
@Roman How did you finally implement it? I need to do something similar for my 64 bit vector. Could you please give me some insight? — Abhishek, Jan 21 '13 at 18:08

score 7 · Answer 1 · answered Mar 30 '12 at 17:43

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)
}

Evgeny Kluev · Accepted Answer · 2012-03-30T17:11:34.593

3

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.

edited Mar 30 '12 at 17:11

answered Mar 30 '12 at 16:54

Evgeny Kluev

24,287
7
55
98

@Evgeny kluev Could you please explain it a bit more. Can such an expression be used to calculate the hamming weight of 64 bit vector? – Abhishek Jan 21 '13 at 18:07
@abhiitd.cs: Such an expression is only useful to calculate Hamming weight of 8-bit word (with pretty strong limitations specified in OP). If you need Hamming weight of 64 bit vector (with the same limitations), you could use the same idea, but the the resulting expression would be much more complicated. If you don't need these limitations, it is more reasonable to extend to 64 bits the solutions for this question: [How to count the number of set bits in a 32-bit integer?](http://stackoverflow.com/q/109023/1009831) – Evgeny Kluev Jan 21 '13 at 18:34
@EvgenyKluev Thanks a lot for your reply. I have actually gone through that link and additionally, I found this paper [Hamming Weight](http://perso.citi.insa-lyon.fr/claurado/ham/overview.pdf) which explains injections to do it in a better parallel way. Actually I have to do a hamming weight calculation of 256 bits, in most efficient way, as it is in the critical path of my hardware design. So I was looking for most efficient solution and your solution looked appalling to me. :) – Abhishek Jan 22 '13 at 17:28
@abhiitd.cs I think it's easier to do in hardware, you can avoid shifts and masks, and use simple adders, half of which don't need carry bits – Sophistifunk Apr 10 '13 at 04:57

Hamming weight written only in binary operations?

2 Answers2

Linked