This does not use the approach from the paper, does it? They had several optimization techniques for this case. First, they counted bits bytewise rather than bitwise, using a lookup table for each byte. Second, they used the rank array to jump over additional positions. We can merge this now, but I guess the performance will not be so great with your current approach. But we can also measure this first and then further improve the code.