How to count number of 1s of the first k positions in a bitset (bitmap)?
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 &lt; 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)$.