Quickest way to get the position of the leading 1 in a bitset for an integer?

Question

Consider this program

#include <iostream>
#include <bitset>
#include <cstdint>
#include <cstdlib>
typedef uint8_t Tnum;
template <typename T>
void printBits(T a)
{
    std::cout << std::bitset<(sizeof(a) * 8)>(a).to_string() << '\n';
}
int main()
{
    printBits(Tnum(15));
    printBits(Tnum(17));
    return EXIT_SUCCESS;
}

it prints

00001111
00010001

Now consider this 2 guys from the previous output

I would like to know how, given a signed or unsigned integer type, and given a value for an instance of that type, I can get the location of that leading 1 in the pattern, starting to count from 0 the result I expect is 3 for the first row, 4 for the second one. The total amount of positions involved is also acceptable to me, like 4 for the first row and 5 for the second one.

I don't have Hacker's Delight or similar text available at the moment and I can't find any quick bit twiddling .

This is kinda it but it's error prone and it will never pass a conversion test or set of warning flags about conversions, at least in my case. Plus it's probably a non-optimal choice.

Please no lookup tables, I'm willing to accept anything that doesn't cause conversion issues and doesn't use a LUT. For C89/99 and C++11 .

score 4 · Answer 1 · answered Jul 26 '14 at 02:20

4

If this is X86 and you can use assembly, there's the bit scan reverse instruction. Depending on the compiler, there may be an intrinsic for this.

bit scan reverse

answered Jul 26 '14 at 02:20

rcgldr

27,407
3
36
61

On GCC it's called `__builtin_clz`. – Brian Bi Jul 26 '14 at 02:30
this sounds really interesting, the problem is that it will probably work based on the size of the native word for the CPU, for example it will probably expect a 32 bit wide integer on most if not all the x86 cpus, that's a waste/problem when you have, let's say, an 8 bit wide unsigned integer or just an integer that is not as large as the native word. – user2485710 Jul 26 '14 at 02:31
3

@user2485710 A shorter integer has to be promoted to a word in order to be pushed onto the stack or passed in a register anyway. – Brian Bi Jul 26 '14 at 02:50
@user2485710: The BSR instruction has 16-, 32-, and 64-bit variants. – TonyK Jul 28 '14 at 08:28

score 2 · Answer 2 · answered Jul 26 '14 at 02:18

2

Why don't you have access to hacker's delight ? Proxy limitation ?

Here is the solution from http://www.hackersdelight.org/hdcodetxt/nlz.c.txt

int nlz1(unsigned x) {
   int n;

   if (x == 0) return(32);
   n = 0;
   if (x <= 0x0000FFFF) {n = n +16; x = x <<16;}
   if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;}
   if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;}
   if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;}
   if (x <= 0x7FFFFFFF) {n = n + 1;}
   return n;
}

answered Jul 26 '14 at 02:18

bokan

3,601
2
23
38

this is basically the same as the other one on the other bit-twiddling site, and it looks so branchy and non-optimal; By the way I didn't knew about the online stuff on the website, thanks for that. – user2485710 Jul 26 '14 at 02:29

chesslover · Answer 3 · 2014-07-29T06:55:48.240

As others have stated, x86-64 processors have the most significant bit (MSB) instruction which can be accessed through compilers using either inline assembly or compiler instructions (intrinsics). The Microsoft C compiler has the _BitScanReverse instruction for 32bits.

An example of how to insert inline assembly code for the gcc compiler may be found here: https://www.biicode.com/pablodev/pablodev/bitscan/master/25/bitboard.h

In case you are not interested in this type of solutions an O(log(N)) solution with a good compromise between table size and speed using a de Bruijn magic number is:

uint32_t v;
int r;
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1;  
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Basically the first shifts round the input number to one less than a power of 2 and then de Bruijn multiplication and lookup does the rest. The shifts are not necessary when it is known that the input number is a power of 2 (the magic number is different though). All information is available here.

score 1 · Answer 4 · answered Jul 26 '14 at 11:08

1

You can use BitScanRevers intrinsic if you're using visual studio.

answered Jul 26 '14 at 11:08

rashmatash

1,699
13
23

Quickest way to get the position of the leading 1 in a bitset for an integer?

4 Answers4