I'm looking for a function that counts the bits in a mpz_class type number:
for example
mpz_class n1=127;
mpz_class n2=5;
mpz_class n3=16;
int w1 = weigth(n1); // 7
int w2 = weigth(n2); // 2
int w3 = weigth(n3); // 1
I want this function weigth() to test really big numbers, but I did not find any,
I might code it myself, but it wont be as efficient.
[C++] GMP hamming weight
Re: [C++] GMP hamming weight
For fixed length integers (e.g. 32 bit ints) there is a well known clever way to do this:
However, as I understand it the mpz_class is an arbitrary length integer, so the above does not apply. This mean you will have to do a loop to count the bits. There is however still a clever way to do it without bit shifting as follows:
Code: Select all
int countBits(unsigned x)
{
x = x  ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
Code: Select all
int countBits(unsigned x)
{
int count = 0;
while( x!=0 ){
++count;
// reset the lowest set bit
x &= x1;
}
return count;
}
_{Jaap's Puzzle Page}

 Posts: 4
 Joined: Mon Jan 19, 2015 9:41 pm
Re: [C++] GMP hamming weight
I found the first algo with google and did not see how to apply it on mpz_class.
anyway, it looks nice, strange and worth a deeper look!
after another search,I found the answer
the method actually exists: mpz_popcount
https://gmplib.org/manual/IntegerLogic ... tFiddling
and I also found how to use it, which was not obvious since I'm new with GMP:
thank you very much for the answer !
anyway, it looks nice, strange and worth a deeper look!
after another search,I found the answer
the method actually exists: mpz_popcount
https://gmplib.org/manual/IntegerLogic ... tFiddling
and I also found how to use it, which was not obvious since I'm new with GMP:
Code: Select all
mpz_class bigNum = 127;
long hammingWeigth = mpz_popcount ( bigNum.get_mpz_t() );
Re: [C++] GMP hamming weight
Since Intel introduced the "Nehalem" architecture CPUs, (circa November 2008), the cores support SSE4.2 which includes the POPCNT machine instruction. It can return the bit count of a 16, 32, or 64 bit register or a 2, 4 or 8 byte field in memory, into a 16, 32 or 64 bit register respectively.
It is probably carrying out the equivalent of jaap's countbits() function above, but at the microcode level.
POPCNT r16, r/m16
POPCNT r32, r/m32
POPCNT r64, r/m64
Note that the return value register, (the first parameter), must be the same size as the register or memory field to be 'POP' counted. e.g.
POPCNT RAX, RCX would count the number of bits in 64 bit register RCX and return the result in the 64 bit register RAX
From C/C++ the 32 and 64 bit instructions can be accessed via the following intrinsics from nmmintrin.h
The 64 bit version must be compiled to an x64 target exe file, which will only run on a 64 bit Windows machine.
It is probably carrying out the equivalent of jaap's countbits() function above, but at the microcode level.
POPCNT r16, r/m16
POPCNT r32, r/m32
POPCNT r64, r/m64
Note that the return value register, (the first parameter), must be the same size as the register or memory field to be 'POP' counted. e.g.
POPCNT RAX, RCX would count the number of bits in 64 bit register RCX and return the result in the 64 bit register RAX
From C/C++ the 32 and 64 bit instructions can be accessed via the following intrinsics from nmmintrin.h
Code: Select all
int _mm_popcnt_u32 (unsigned int a);
int _mm_popcnt_u64 (unsigned __int64 a);
Code: Select all
#include "stdafx.h"
#include <nmmintrin.h>
int main()
{
unsigned __int64 x = 123456789;
printf("%d\n", _mm_popcnt_u64(x));
return 0;
}