-
-
Save sycue/31c27962980ac18e2ee2ab8793a68bdc to your computer and use it in GitHub Desktop.
NextHammingWeight - a function for finding the next int with the same hamming weight
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* I was searching for an algorithm that gave you the next integer (counting | |
* upwards) that has the same hamming weight as the current number, and I | |
* couldn't find anything. So here's a function that does that for you. If | |
* there is no 'next number' (i.e. this is the largest number that has this | |
* hamming weight), it simply returns the same number again. | |
* | |
* This can probably be optimized; I whipped it up pretty quickly. Relatedly, I | |
* only tested a few edge cases I could think of, so if you use this, be sure | |
* to test it more thoroughly. | |
* | |
* Usage: call NextHammingWeight((unsigned int) <number>) | |
* | |
* Licence: Public domain. | |
*/ | |
int HammingWeight (unsigned int number) { | |
int i; | |
int c = 0; | |
for (i=0; i<sizeof(int)*8; i++) { | |
if ((number >> i) & 0x1) { | |
c++; | |
} | |
} | |
return c; | |
} | |
unsigned int NewNumber (int ones) { | |
unsigned int result = 0x1; | |
result = result << ones; | |
result--; | |
return result; | |
} | |
unsigned int NextHammingWeight (unsigned int current) { | |
unsigned int next = current; | |
int i; | |
for (i=0; i<sizeof(int)*8-1; i++) { | |
if (((next>>i)&0x3) == 0x1) { | |
// If the two bits being looked at are '01', switch them | |
next = next ^ (0x3 << i); | |
// We then have to 'reset' all of the bits before the switch. | |
int ones = HammingWeight(next % (0x2 << i)); | |
next &= ~((0x2 << i) - 1); // zero those bits | |
next |= NewNumber(ones); // 'reset' the bits | |
break; | |
} | |
} | |
return next; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment