Questions tagged [hammingweight]
The Hamming weight of a positive integer is the count of one bits in its binary representation.
hammingweight
70
questions
1013
votes
66
answers
648k
views
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?
92
votes
24
answers
53k
views
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 ...
- 5,161
29
votes
8
answers
6k
views
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 ...
- 48.3k
23
votes
4
answers
8k
views
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) * ...
- 808
19
votes
8
answers
46k
views
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 ...
- 245
16
votes
4
answers
4k
views
.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
...
- 48.3k
14
votes
10
answers
15k
views
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 ...
- 36.3k
14
votes
3
answers
11k
views
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
...
- 141
14
votes
9
answers
10k
views
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 ...
- 12.4k
13
votes
2
answers
3k
views
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....
- 1,413
13
votes
4
answers
9k
views
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 ...
- 115k
12
votes
4
answers
11k
views
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 ...
- 8,210
12
votes
3
answers
12k
views
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....
- 131
11
votes
1
answer
1k
views
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 ...
- 11.5k
9
votes
8
answers
30k
views
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 ...
- 66.6k
9
votes
2
answers
2k
views
Fast popcount on Intel Xeon Phi
I'm implementing an ultra fast popcount on Intel Xeon® Phi®, as it's a performance hotspot of various bioinformatics software.
I've implemented five pieces of code,
#if defined(__MIC__)
#include <...
- 93
7
votes
2
answers
1k
views
What is the fastest algorithm to computer all permutations of a binary number with same hamming weight?
I want an algorithm to compute all permutations of a fixed size binary number with a given hamming weight. For example, if the hamming weight is 2 and the binary size is 4 then there are these outputs:...
- 558
6
votes
3
answers
7k
views
std::bitset<N>::count vs __builtin_popcount
Comparing the following two expressions
std::bitset<8>(5).count()
__builtin_popcount(5)
which one is better?
- 3,220
6
votes
2
answers
793
views
Bit-Count or Hamming-weight of a BitString in Elixir?
Please how can we efficiently calculate the hamming-weight of a bit-string in elixir?
Example: 0b0101101001 has a Hamming-weight of 5 (i.e. 5 bits set)
My Attempt:
iex> Enum.count(Integer....
- 10.7k
6
votes
5
answers
10k
views
Counting the number of bits that are set
I want to count the number of bits in a binary number that are set.
For example, user enter the number 97 which is 01100001 in binary. The program should give me that 3 bits are set using MIPS ISA.
I ...
- 5,227
5
votes
9
answers
15k
views
NASM: Count how many bits in a 32 Bit number are set to 1
I have a 32 Bit number and want to count know how many bits are 1.
I'm thinking of this pseudocode:
mov eax, [number]
while(eax != 0)
{
div eax, 2
if(edx == 1)
{
ecx++;
}
shr eax, 1
}
...
- 19.2k
5
votes
3
answers
4k
views
Checking CPU Popcount from C#
Does anyone know how to check from C# whether the CPU supports popcount (population count)?
I'm trying to port some chess code from C++ to C#.
- 131
5
votes
3
answers
6k
views
How do I enable the SSE4.2 instruction set in Visual C++?
I am using the BRIEF descriptor in OpenCV in Visual C++ 2010 to match points in two images.
In the paper about the BRIEF-descriptor is written that it is possible to speed up things:
"The BRIEF ...
- 151
5
votes
3
answers
688
views
Popcount assembly / sum indexes of set bits
I want to sum all indexes of set bits.
http://bitmath.blogspot.com/2023/01/weighted-popcnt.html?m=1
has an interesting implementation:
// sum of indexes of set bits
int A073642(uint64_t n)
{
...
user21777985
4
votes
5
answers
2k
views
How many 1s in an n-bit integer?
An interesting problem I ran into today: what is the fastest way to count the number of 1s in an n-bit integer? Is it possible to beat O(n)?
For example:
42 = 0b101010 => 3 ones
512 = ...
- 50.2k
3
votes
1
answer
480
views
Why does my Hamming weight function work in C but not in Rust?
I've got the following Hamming weight code in Rust, and it returns garbage for 0xffff and 0xffffffff, but the identical code in C works, so I must be misunderstanding something about how Rust does bit-...
- 707
3
votes
2
answers
2k
views
Number of set elements in column of type SET (population count)
I have a table declaration like
CREATE TABLE my_foos (
id INT NOT NULL AUTO_INCREMENT,
bars SET('one', 'two', 'three', 'four', 'five') NOT NULL
)
And the values
1, ('one', 'two')
2, ('two')
...
- 25.7k
3
votes
1
answer
983
views
Efficiently calculate hamming weight
I'm on an apple m1 processor.
What i'm trying to do is efficiently count the 1 bits in a large char array in rust. I looked up the arm neon instructions, and I think I can do it via a cnt instruction ...
- 1,312
3
votes
1
answer
223
views
Bijection between (n choose k) and bitstrings of length n with k bits set
While I know how to generate all (n choose k) bitstrings of size n with exactly k bits set to one, I'm struggling finding a bijection, that gets as input a number i between 1 and (n choose k) and ...
- 317
3
votes
1
answer
856
views
How does this magic bit counting method work?
While working on the XKCD April Fool's skein hash collision problem I ran across this strange, fast, multiplicative method of counting the set bits in a word:
c = (v * 0x200040008001ULL & ...
- 597
3
votes
1
answer
4k
views
Calculate Hamming weight and/or distance in VBA Excel
I’m trying to compare clients, two by two, whose qualities can be defined by binary choices (for example a client uses a product or not).
After much search online, it looks like I’d need to use the ...
- 195
2
votes
4
answers
2k
views
Hamming weight ( number of 1 in a number) mixing C with assembly
I'm trying to count how many number 1, are in the numbers of an array.
First I have a code in C lenguaje(work ok):
int popcount2(int* array, int len){
int i;
unsigned x;
int result=0;
...
- 191
2
votes
5
answers
2k
views
Hamming weight/population count in T-SQL
I'm looking for a fast way to calculate the hamming weight/population count/"the number of 1 bits" of a BINARY(1024) field. MySQL has a BIT_COUNT function that does something like that. I couldn't ...
- 1,851
2
votes
4
answers
851
views
counting the difference in bits when comparing two numbers in Lua
I would like to compare two numbers to determine the number of bits which must be flipped in order make them equal.
For instance, 5 and 6 would require 2 bit flips.
I can do this manually, but ...
- 831
2
votes
4
answers
509
views
Do these two bit-counting algorithms have the same time complexity?
Below is an algorithm I picked up somewhere (forgot where exactly, possibly from this answer) to calculate the amount of bits set in an integer, i.e. its Hamming weight.
function hamming_weight($i)
{
...
- 1,228
2
votes
2
answers
931
views
Count integers in [1..N] with K zero bits below the leading 1? (popcount for a contiguous range without HW POPCNT)
I have following task:
Count how many numbers between 1 and N will have exactly K zero non-leading bits. (e.g. 710=1112 will have 0 of them, 4 will have 2)
N and K satisfy condition 0 ≤ K, N ≤ ...
- 107
2
votes
1
answer
1k
views
Population count in AVX512
I have been trying to use _mm256_popcnt_epi64 on a machine that supports AVX512 and on code that has previously been optimiized for AVX2.
Unfortunately, I ran into the issue that the function isn't ...
- 58
2
votes
1
answer
709
views
Find next number with specific hamming weight
Given a certain integer x, I wish to compute the next higher integer y which has a certain hamming weight w. Mind that the hamming weight of x does not have to be w as well.
So, for example x = 10 (...
- 65
2
votes
1
answer
273
views
Why shouldn't I catch Undefined Instruction exception instead of using CPUID?
Assume I want to use an instruction that may be not available. And this instruction is not of those transparent fallback, it is undefined instruction when it is not available. Say it is popcnt for ...
- 12.7k
1
vote
2
answers
3k
views
Hamming weight for a list of integers in Matlab [duplicate]
Quite a simple problem: I have a list of integers, e.g.,
a = [7 8]
Now I want to have a seperate list, that contains the Hamming Weight (that is the
number of 1 bits in the binary represenation) ...
- 999
1
vote
2
answers
282
views
Matlab: index array by Hamming Weights
a contains indices and their occurrences. Now the indexing needs to be changed with Hamming weight so that indices with equal hamming weight will be summed up. How to do the Hamming weight indexing? ...
- 51.7k
1
vote
1
answer
55
views
YASM is there a way to check for specific numbers in a word?
If I were to try to calculate the number of 1's in the dw data, how would I go about that? I want to store the number of 1's in memory sum. I am using EBE to code in 64 bit Assembly Language.
segment ....
- 27
1
vote
1
answer
636
views
MIPS assembly code - trying to find out what this code's about
I'm learning assembly code, and given this code, I need to find what this code is about. However I am trying to debug using qtspim. I know what the value inside each register, but I still don't get ...
- 145
1
vote
1
answer
382
views
Generate integers with even hamming weight (popcount) c++
I want to effectively (by using bit hacks) generate all integers up a given number, k, such that they have an even hamming weight without explicitly calculating their hamming weights. It is not ...
1
vote
3
answers
3k
views
How to make smoother wave by apply hamming window?
I have try to make the smoother wave (from stock price)
but I don't know how to apply it to my wave.
import numpy as np
wave = [1575.7918235085228, 1574.2183726917613, 1571.9212868430398, 1569....
- 511
1
vote
1
answer
435
views
Looking for a more efficient pop count given a restriction
The popcount function returns the number of 1's in an input. 0010 1101 has a popcount of 4.
Currently, I am using this algorithm to get the popcount:
private int PopCount(int x)
{
x = x - ((x &...
- 11.5k
1
vote
1
answer
2k
views
calculate hamming distance and weight in sqlite
Is there a good way to calculate hamming distance and weight in sqlite? It supports bit-wise operators but I want to order results based on hamming weight, and there is no support for bitcount in ...
- 2,101
1
vote
0
answers
271
views
Can I get a POPCNT on a YMM register? [duplicate]
I'm vectorizing some image processing code using 32 bit hand-written assembly to access AVX2 instructions. However I've run into a roadblock. The results of the vector operations end up in a YMM ...
- 253
1
vote
2
answers
2k
views
How to calculate how many bits in a decimal number is 1?
This program I created in RISC-V RARS 1.3 application is designed to take a decimal number and count how many bits are in that number. The one I am testing is the decimal number 5, and this program ...
- 11
1
vote
0
answers
165
views
SICStus Prolog: FFI slow, how to calculate Hamming weight fast?
When I ran the foreign code sample c1/2, as shown in the SICStus Prolog 4.3.2 manual, and compared its runtime to the corresponding Prolog code Y is X+9, I got strange timing results:
p(N, X) :- ( ...
- 18.6k