Extract n most significant non-zero bits from int in C++ without loops

Question

I want to extract the n most significant bits from an integer in C++ and convert those n bits to an integer.

For example

int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000

Now I want to extract the 4 most significant digits from that representation, i.e. 1111

00000000000000000000010010110000
                     ^^^^

and convert them again to an integer (1001 in decimal = 9).

How is possible with a simple c++ function without loops?

Megathere

Obligatory link: graphics.stanford.edu/~seander/bithacks.html. – Sideman

You're looking for the first n bits which start with a 1 bit. This is not the same as the n most significant bits. The 4 most significant bits in your example are all 0s. – Quill

As I understand it, that is the most significant bits. You ignore leading 0s as if they don't exist. I.e. purely in decimal now, what is 12345000 to 2 significant digits? What about 000012345000? – Sobel

@BoBTFish: My understanding is that a bit (in fact, any digit) is more significant the further "left" it's written, no matter what value (zero or one, in this case) it has. I think it's more significant the further 'left' it is because changing the digit more significantely changes the total value than changing a digit further right. – Twinkling

@Ferruccio: "significant bits" could have either meaning, and the question clearly describes what is meant here. – Herbart

Answer 1

Some processors have an instruction to count the leading binary zeros of an integer, and some compilers have instrinsics to allow you to use that instruction. For example, using GCC:

uint32_t significant_bits(uint32_t value, unsigned bits) {
    unsigned leading_zeros = __builtin_clz(value);
    unsigned highest_bit = 32 - leading_zeros;
    unsigned lowest_bit = highest_bit - bits;

    return value >> lowest_bit;
}

For simplicity, I left out checks that the requested number of bits are available. For Microsoft's compiler, the intrinsic is called __lzcnt.

If your compiler doesn't provide that intrinsic, and you processor doesn't have a suitable instruction, then one way to count the zeros quickly is with a binary search:

unsigned leading_zeros(int32_t value) {
    unsigned count = 0;
    if ((value & 0xffff0000u) == 0) {
        count += 16;
        value <<= 16;
    }
    if ((value & 0xff000000u) == 0) {
        count += 8;
        value <<= 8;
    }
    if ((value & 0xf0000000u) == 0) {
        count += 4;
        value <<= 4;
    }
    if ((value & 0xc0000000u) == 0) {
        count += 2;
        value <<= 2;
    }
    if ((value & 0x80000000u) == 0) {
        count += 1;
    }
    return count;
}

Herbart

Thanks, that's definitely the function I was looking for! It's exactly what I meant. I modified the uint32_t type to simply int because I know here size is 8 byte for integers. (p.s. compiled on g++4.5 x86_64 Linux) – Megathere

Answer 2

It's not fast, but (int)(log(x)/log(2) + .5) + 1 will tell you the position of the most significant non-zero bit. Finishing the algorithm from there is fairly straight-forward.

Colicroot

It involves floating point arithmetic...i don't want to use floating point values... – Megathere

Answer 3

This seems to work (done in C# with UInt32 then ported so apologies to Bjarne):

        unsigned int input = 1200;
        unsigned int most_significant_bits_to_get = 4;
        // shift + or the msb over all the lower bits
        unsigned int m1 = input | input >> 8 | input >> 16 | input >> 24;
        unsigned int m2 = m1 | m1 >> 2 | m1 >> 4 | m1 >> 6;
        unsigned int m3 = m2 | m2 >> 1;
        unsigned int nbitsmask = m3 ^ m3 >> most_significant_bits_to_get;

        unsigned int v = nbitsmask;
        unsigned int c = 32; // c will be the number of zero bits on the right
        v &= -((int)v);
        if (v>0) c--;
        if ((v & 0x0000FFFF) >0) c -= 16;
        if ((v & 0x00FF00FF) >0) c -= 8;
        if ((v & 0x0F0F0F0F) >0 ) c -= 4;
        if ((v & 0x33333333) >0) c -= 2;
        if ((v & 0x55555555) >0) c -= 1;

        unsigned int result = (input & nbitsmask) >> c;

I assumed you meant using only integer math.

I used some code from @OliCharlesworth's link, you could remove the conditionals too by using the LUT for trailing zeroes code there.

Refreshing