Algorithm to count how many "1" in binary o(1)
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
Read this - http://en.wikipedia.org/wiki/Hamming_weight[^]
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V) תפסיק לספר לה' כמה הצרות שלך גדולות, תספר לצרות שלך כמה ה' גדול!
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
There are several algorithms listed here[^]. For a 32-bit integer, you probably want "Counting bits set, in parallel[^]":
int CountBitsSet(int v)
{
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}Just don't ask me to explain how it works! :-O
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
"These people looked deep within my soul and assigned me a number based on the order in which I joined" - Homer
-
There are several algorithms listed here[^]. For a 32-bit integer, you probably want "Counting bits set, in parallel[^]":
int CountBitsSet(int v)
{
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}Just don't ask me to explain how it works! :-O
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
Richard Deeming wrote:
Just don't ask me to explain how it works!
How, how indeed...http://en.wikipedia.org/wiki/Hamming_weight[^]
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V) תפסיק לספר לה' כמה הצרות שלך גדולות, תספר לצרות שלך כמה ה' גדול!
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
-
Read this - http://en.wikipedia.org/wiki/Hamming_weight[^]
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V) תפסיק לספר לה' כמה הצרות שלך גדולות, תספר לצרות שלך כמה ה' גדול!
Thank you for the answer. This is the answer I was looking for. Thank for the other for the answers.
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
Member 11055093 wrote:
I've been told I can do it using space as much as I need.
Fastest way with unlimited space would be a lookup table.
-
There are several algorithms listed here[^]. For a 32-bit integer, you probably want "Counting bits set, in parallel[^]":
int CountBitsSet(int v)
{
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}Just don't ask me to explain how it works! :-O
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
-
for example: 9 = 1001 in binary so the function GetNumOfBinary(9) = 2. I know I can do it in o(n) (time) by convert it to binary and exam digit by digit. I've been told I can do it using space as much as I need. How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))
It depends on your abstract model. With the usual model, you can't do any better than O(n) (so o(n) is not happening, or did you write a lower case o by accident?) - obviously on a plain old Turing machine, you're going to have to read every bit. But this problem is in NC. You could sum n/2 pairs of bits, then n/4 pairs of "2bit numbers", n/8 pairs of nibbles, etc, and you're done in log n steps, with each step taking logarithmic time too (adders) (sometimes not counted), all with a polynomial number of processing elements. Similarly in "broadword computing", you would say that you could compute this in O(log n) broadword steps - using the same construction, but now every layer is a couple of steps (mask and add) (with the addition counted as 1 step, instead of as a circuit of depth O(log n)) Practically, on 32bit words but "pretending 32 is not a constant", you can still use the same construction for an O(log n) algorithm possibly with a multiplication trick to do several sums at once (already shown in answers) or lookup tables or (with as much space as you need, you could cheat terribly and compute any mapping from 32bit integers to anything in a single step), if available, the
popcntinstruction. For arrays you could use a pshufb-based trick[^] (pshufb is awesome).
