0
$\begingroup$

Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.

Output: the total number of 1s in the first $k$ position of $b$.

Obviously it can be done in $O(k)$, is there any more efficient way in C++ such as $O(\frac{k}{W})$, where $W$ is the word size of the machine? Note that the popcount instruction only works when $k=L$, but $k$ is varying.

$\endgroup$
  • $\begingroup$ "popcount" should be a useful Google term. It can be done in $O(\log W)$ time with a kind of "horizontal addition" that first adds $W/2$ adjacent pairs of bits, then $W/4$ adjacent 2-bit blocks, then $W/8$ adjacent 4-bit blocks, etc. To limit to the first $k$ bits, first AND with an appropriate mask, which can be formed by shifting the value 1 left $k$ times and then subtracting 1. $\endgroup$ – j_random_hacker Jun 1 '18 at 15:18
  • $\begingroup$ @j_random_hacker Surely that mask would get you the lowest $k$ bits? (Of course you could just NOT it first.) $\endgroup$ – Draconis Jun 1 '18 at 16:04
  • $\begingroup$ @Draconis: I usually index bits so that the lowest is position 0, but if you make the highest bit position 0, then yes you could NOT first (or just shift -1 left to start with). $\endgroup$ – j_random_hacker Jun 1 '18 at 16:32
2
$\begingroup$

Popcount is going to be your best option here. As j_random_hacker mentions in a comment, popcount on a single word can be done in $O(\log W)$ time if implemented by hand, or $O(1)$ if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again, $W$ should also be a constant for any given machine).

(Note: if $b$ is longer than a single word, then you can just use popcount directly on the first $\lfloor \frac{k}{W} \rfloor$ words, and ignore the last however many others, in $O(\frac{k}{W})$. It's only the one word in the middle that you need any fancy algorithm for. So I'm going to be solving the special case where $k < W$. If this isn't the case, which it normally won't be, then replace $k$ with $k \bmod W$.)

The part that depends on $k$ is getting rid of the $W-k$ unneeded bits. One way to do this is masking: generate a mask of $k$ ones, then AND your value with it. (You can generate such a mask by starting with 1, left-shifting $k$ times, then subtracting 1 and taking the complement. Or you can start with only the highest bit set and arithmetic-right-shift $k$ times.)

Another way is to just push the unneeded bits off the end of the word: logical-right-shift your number $W-k$ times and the unwanted bits will be gone.

Which of these is most efficient depends on the specifics of your machine. If it can do bitwise operations and variable shifts in a constant number of clock cycles, then the whole thing is still $O(1)$. If it can't do variable shifts, then it takes $O(k)$; if it can't do constant-time bitwise operations, then there's no way to get better than $O(W)$.

$\endgroup$
  • $\begingroup$ thanks, do you mean $l-k$ instead of $W-k$, since $W$ is the size of a word in the machine. Besides, to summary your suggestion, it the machine allows, I can do it in two steps: $b = b >> (l-k); b.popcount();$, is it what you mean? $\endgroup$ – Keith Jun 1 '18 at 18:17
  • $\begingroup$ @D.W. You're right. Clarified that: if $k > W$, then you just use popcount directly on the first however many words, ignore the last however many words, and use my algorithm on the one word in the middle. $\endgroup$ – Draconis Jun 1 '18 at 20:37
  • $\begingroup$ @Keith Updated the answer; is that a bit clearer? Basically you'll want to do exactly that, but only on a single word. For all the rest of the words you either popcount them or ignore them. $\endgroup$ – Draconis Jun 1 '18 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.