Unset the most significant bit in a word (int32) [C]

Question

How can I unset the most significant setted bit of a word (e.g. 0x00556844 -> 0x00156844)? There is a __builtin_clz in gcc, but it just counts the zeroes, which is unneeded to me. Also, how should I replace __builtin_clz for msvc or intel c compiler?

Current my code is

 int msb = 1<< ((sizeof(int)*8)-__builtin_clz(input)-1);
 int result = input & ~msb;

UPDATE: Ok, if you says that this code is rather fast, I'll ask you, how should I add a portability to this code? This version is for GCC, but MSVC & ICC?

Mahler

"the most significant setted bit of a word", is that the 22nd-bit? that what I can see in your example – Doone

No, it is the most significant bit that is set in the given int. For 0x12345678 result will be 0x02345678; for 0x00000123 -> 0x00000023 – Mahler

Your implementation is quite efficient, actually it's better than in my answer, as the compiler will optimize the subtraction away – Spinozism

For portability, you should also use (sizeof(int)*CHAR_BIT) (CHAR_BIT is in limits.h) instead of (sizeof(int)*8). – Dillard

David X, thanks, but so wide portability is not needed. Portability interested is only between most common x86 & x86_64 compilers. This code will be used by small number of users, on the desktops and small clusters. – Mahler

Answer 1

Just round down to the nearest power of 2 and then XOR that with the original value, e.g. using flp2() from Hacker's Delight:

uint32_t flp2(uint32_t x) // round x down to nearest power of 2
{
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >>16); 
    return x - (x >> 1); 
}

uint32_t clr_msb(uint32_t x) // clear most significant set bit in x
{
    msb = flp2(x);  // get MS set bit in x
    return x ^ msb; // XOR MS set bit to clear it
}

Westbound

@osgx: it depends on what CPU you want to run it on - not all CPUs have a count leading zeroes instruction or equivalent. And of course there is also the issue of portability... – Westbound

My primary CPU are x86 (Core2) and possibly x86_64 (Core2), with clz instruction. Portability interested is only between most common x86 & x86_64 compilers. – Mahler

Answer 2

If you are truly concerned with performance, the best way to clear the msb has recently changed for x86 with the addition of BMI instructions.

In x86 assembly:

clear_msb:
    bsrq    %rdi, %rax
    bzhiq   %rax, %rdi, %rax
    retq

Now to rewrite in C and let the compiler emit these instructions while gracefully degrading for non-x86 architectures or older x86 processors that don't support BMI instructions.

Compared to the assembly code, the C version is really ugly and verbose. But at least it meets the objective of portability. And if you have the necessary hardware and compiler directives (-mbmi, -mbmi2) to match, you're back to the beautiful assembly code after compilation.

As written, bsr() relies on a GCC/Clang builtin. If targeting other compilers you can replace with equivalent portable C code and/or different compiler-specific builtins.

#include <inttypes.h>
#include <stdio.h>

uint64_t bsr(const uint64_t n)
{
        return 63 - (uint64_t)__builtin_clzll(n);
}

uint64_t bzhi(const uint64_t n,
              const uint64_t index)
{
        const uint64_t leading = (uint64_t)1 << index;
        const uint64_t keep_bits = leading - 1;
        return n & keep_bits;
}

uint64_t clear_msb(const uint64_t n)
{
        return bzhi(n, bsr(n));
}

int main(void)
{
        uint64_t i;
        for (i = 0; i < (uint64_t)1 << 16; ++i) {
                printf("%" PRIu64 "\n", clear_msb(i));
        }
        return 0;
}

Both assembly and C versions lend themselves naturally to being replaced with 32-bit instructions, as the original question was posed.

Lifeline

Wiki says that BMI extension is available from Haswell en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets. Can I use it in 32-bit mode x86 and in 64-bit x86_64 mode? Is there any builtins for bsrq/bzhiq? (recent Clang/gcc portability is ok) – Mahler

@Mahler For 32-bit instructions you can swap out the 'q' suffixes in the assembly for 'l'. Or in the C version, wherever you see uint64_t swap in uint32_t. As for builtins with bsr/bzhi, there are intrinsics available (including "immintrin.h") in GCC/Clang which allow you to use BMI instructions natively, although your code will not gracefully degrade -- it will trap as illegal instructions on hardware that doesn't support BMI. Don't be too concerned about the verbosity of the C code: it actually does compile down to only bsr/bzhi when you add -mbmi -mbmi2 and have a Haswell or newer CPU. – Lifeline

Answer 3

You can do

unsigned resetLeadingBit(uint32_t x) {
    return x & ~(0x80000000U >> __builtin_clz(x))
}

For MSVC there is _BitScanReverse, which is 31-__builtin_clz().

Actually its the other way around, BSR is the natural x86 instruction, and the gcc intrinsic is implemented as 31-BSR.

Spinozism