[C++] GMP hamming weight

In this forum members can discuss topics about specific programming languages.
Post Reply
m3m3p4sm4l
Posts: 4
Joined: Mon Jan 19, 2015 9:41 pm

[C++] GMP hamming weight

Post by m3m3p4sm4l » Sun Feb 01, 2015 1:51 pm

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.

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: [C++] GMP hamming weight

Post by jaap » Sun Feb 01, 2015 4:48 pm

For fixed length integers (e.g. 32 bit ints) there is a well known clever way to do this:

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;
}
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)
{
    int count = 0;
    while( x!=0 ){
        ++count;
        // reset the lowest set bit
        x &= x-1;
    }
    return count;
}

m3m3p4sm4l
Posts: 4
Joined: Mon Jan 19, 2015 9:41 pm

Re: [C++] GMP hamming weight

Post by m3m3p4sm4l » Sun Feb 01, 2015 5:44 pm

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/Integer-Logic ... t-Fiddling

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() );
thank you very much for the answer !

User avatar
stephj
Posts: 5
Joined: Sun Apr 13, 2014 5:22 pm
Location: Lancashire, UK

Re: [C++] GMP hamming weight

Post by stephj » Wed Jul 13, 2016 10:16 am

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

Code: Select all

int _mm_popcnt_u32 (unsigned int a); 
int _mm_popcnt_u64 (unsigned __int64 a); 
The 64 bit version must be compiled to an x64 target exe file, which will only run on a 64 bit Windows machine.

Code: Select all

#include "stdafx.h"
#include <nmmintrin.h>

int main()
{
	unsigned __int64 x = 123456789;
	printf("%d\n", _mm_popcnt_u64(x));
	return 0;
}
Image

Post Reply