Stack Overflow
Stack Overflow

Questions tagged [hammingweight]

The Hamming weight of a positive integer is the count of one bits in its binary representation.

The Hamming weight of a positive integer is the count of one bits in its binary representation.

A common synonym is "population count", hence the common function name popcount.

69 questions
1007
votes
65 answers

Count the number of set bits in a 32-bit integer

8 bits representing the number 7 look like this: 00000111 Three bits are set. What are the algorithms to determine the number of set bits in a 32-bit integer?
Matt Howells
  • 40,310
  • 20
  • 83
  • 102
87
votes
24 answers

Elegantly determine if more than one boolean is "true"

I have a set of five boolean values. If more than one of these are true I want to excecute a particular function. What is the most elegant way you can think of that would allow me to check this condition in a single if() statement? Target language…
Ola Tuvesson
  • 5,062
  • 2
  • 28
  • 37
29
votes
8 answers

Optimizing Long.bitCount

I have a program that is making a huge number of calls to Long.bitCount(), so many that it is taking 33% of cycles on one CPU core. Is there a way to implement it that is faster than the Sun JDK version? I have tried: This algorithm (I think this…
finnw
  • 47,861
  • 24
  • 143
  • 221
23
votes
4 answers

How does this algorithm to count the number of set bits in a 32-bit integer work?

int SWAR(unsigned int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } I have seen this code that counts the number of bits equals to 1 in…
Gaith
  • 798
  • 8
  • 19
18
votes
8 answers

Fastest way to count number of 1s in a register, ARM assembly

So I had an interview question before regarding bit manipulation. The company is a well known GPU company. I had very little background in assembly language (weird despite being a phd student in computer architecture) and as this narrative would…
dean
  • 235
  • 1
  • 2
  • 8
16
votes
4 answers

.NET equivalent of Java's Integer.bitCount?

Is there a method similar to Java's Integer.bitCount(int) or Long.bitCount(long) anywhere in the .NET Framework? (For those unfamiliar with these Java methods) this is also known as: Hamming Weight Population Count (often called POPCNT when…
finnw
  • 47,861
  • 24
  • 143
  • 221
14
votes
9 answers

How can I check Hamming Weight without converting to binary?

How can I get the number of "1"s in the binary representation of a number without actually converting and counting ? e.g. def number_of_ones(n): # do something # I want to MAKE this FASTER (computationally less complex). c = 0 …
Pratik Deoghare
  • 35,497
  • 30
  • 100
  • 146
14
votes
3 answers

How to generate a sse4.2 popcnt machine instruction

Using the c program: int main(int argc , char** argv) { return __builtin_popcountll(0xf0f0f0f0f0f0f0f0); } and the compiler line (gcc 4.4 - Intel Xeon L3426): gcc -msse4.2 poptest.c -o poptest I do NOT get the builtin popcnt insruction rather…
Alan Moskowitz
  • 141
  • 1
  • 1
  • 3
14
votes
9 answers

Calculating Hamming weight efficiently in matlab

Given a MATLAB uint32 to be interpreted as a bit string, what is an efficient and concise way of counting how many nonzero bits are in the string? I have a working, naive approach which loops over the bits, but that's too slow for my needs. (A…
nsanders
  • 12,250
  • 2
  • 40
  • 47
13
votes
4 answers

Bit popcount for large buffer, with Core 2 CPU (SSSE3)

I'm looking for the fastest way to popcount on large buffer of 512 or more bytes. I can guarantee any required alignment, and the buffer size is always a power of 2. The buffer corresponds to block allocations, so typically the bits are either all…
Matt Joiner
  • 112,946
  • 110
  • 377
  • 526
13
votes
2 answers

Hamming weight based indexing

Assume we have a integer of bitsize n=4; The problem I am describing is how you would go about indexing a number to an array position based on the Hamming weight and its value knowing the bitsize. E.g. An array with 16 elements for bitsize 4…
1-----1
  • 1,373
  • 8
  • 26
12
votes
4 answers

Fast counting the number of set bits in __m128i register

I should count the number of set bits of a __m128i register. In particular, I should write two functions that are able to count the number of bits of the register, using the following ways. The total number of set bits of the register. The number…
enzom83
  • 8,080
  • 10
  • 68
  • 114
11
votes
2 answers

what's the difference between __builtin_popcountll and_mm_popcnt_u64?

I was trying to how many 1 in 512MB memory and I found two possible methods, _mm_popcnt_u64() and __builtin_popcountll() in the gcc builtins. _mm_popcnt_u64() is said to use the CPU introduction SSE4.2，which seems to be the fastest, and…
stonyliu
  • 111
  • 1
  • 2
  • 6
11
votes
1 answer

How to call a CPU instruction from C#?

My processor (Intel i7) supports the POPCNT instruction and I would like to call it from my C# application. Is this possible? I believe I read somewhere that it isn't, but the JIT will invoke it if it finds it available but what function would I…
Ryan Peschel
  • 11,087
  • 19
  • 74
  • 136
9
votes
8 answers

C code to count the number of '1' bits in an unsigned char

I need C code to return the number of 1's in an unsigned char in C. I need an explanation as to why it works if it's not obvious. I've found a lot of code for a 32-bit number but not much for an unsigned char.
rlbond
  • 65,341
  • 56
  • 178
  • 228
1
2 3 4 5