Strip leading zeroes in binary number in C/C++

Question

Given an integer, how do I strip the leading zeroes off its binary representation?

I am using bit-wise operators to manipulate its binary representation. I am trying to see if an integer is a palindrome in its binary representation. I know there are different solutions out there but I wanted to compare the first and last bit, second and last but one bit and so on. So, I was wondering how to strip those leading 0's for this int.

Perhaps a silly question, but how are your getting its binary representation? — user7116, Apr 27 '12 at 01:45
Using bit-wise operators to manipulate its binary representation. I am trying to see if an integer is a palindrome in its binary representation. I know there are different solutions out there but I wanted to compare the first and last bit, second and last but one bit and so on. So, I was wondering how to strip those leading 0's for this int. — Bugaboo, Apr 27 '12 at 01:51
You could try converting it to a string and using `std::string::find_first_not_of`. — chris, Apr 27 '12 at 01:54
I could but that would beat the purpose of checking this efficiently using bit-wise operators. — Bugaboo, Apr 27 '12 at 02:04
Duplicate. Check out this link: http://stackoverflow.com/questions/845772/how-to-check-if-the-binary-representation-of-an-integer-is-a-palindrome — JKD, Apr 27 '12 at 04:52

score 2 · Answer 1 · answered Apr 27 '12 at 02:09

2

You can use BitScanForward and BitScanReverse (the exact names vary by compiler) to efficiently trim (well, skip processing of) zeros from either side.

answered Apr 27 '12 at 02:09

Ben Voigt

277,958
43
419
720

Hi Ben, can you check if BitScanForward is really the function *f(x)* used to solve [this prefix problem](https://math.stackexchange.com/a/2892097/70274)? (see penultimate paragraph at "conclusion"). – Peter Krauss Aug 23 '18 at 13:34
@PeterKrauss: `BitScanReverse` is definitely useful for solving that with no loop, but your description isn't accurate. `BitScanReverse` tells you how far to shift; it doesn't return the shifted number. – Ben Voigt Aug 23 '18 at 13:46

score 1 · Answer 2 · answered Apr 27 '12 at 02:55

You can find the first bit set by finding the log base 2 of the number:

/* from Bit Twiddling Hacks */
static const unsigned 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
};

uint32_t pos = value;
pos |= pos >> 1;
pos |= pos >> 2;
pos |= pos >> 4;
pos |= pos >> 8;
pos |= pos >> 16;
pos = MultiplyDeBruijnBitPosition[(uint32_t)(pos * 0x07C4ACDDU) >> 27];

Or if you need a mask, just adapt finding the next power of 2:

/* adapted from Bit Twiddling Hacks */
uint32_t mask = value - 1;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;

`0x07C4ACDDU` Can you cite your sources? – ildjarn Apr 27 '12 at 04:25 — ildjarn, Apr 27 '12 at 04:25

score 1 · Answer 3 · answered Jun 29 '16 at 19:02

If you don't mind using strings and performance isn't an issue you can do this:

    #include <bitset>
    #include <string>
    using namespace std;

    // your number
    int N;
    ...

    // convert to a 32 bit length binary string
    string bitstr = bitset<32>(N).to_string();

    // get the substring
    int index = 0;
    string strippedstr;
    for(unsigned int i = 0; i < bitstr.length(); ++i) {
        if(bitstr[i] == '1') {
            index = i;
            break;
        }
    }
    strippedstr = bitstr.substr(index);
   ...

score 0 · Answer 4 · edited May 23 '17 at 11:52

Here's the answer posted in How to check if the binary representation of an integer is a palindrome?

You first reverse the bits using this function:

/* flip n */
unsigned int flip(unsigned int n)
{
    int i, newInt = 0;
    for (i=0; i<WORDSIZE; ++i)
    {
        newInt += (n & 0x0001);
        newInt <<= 1;
        n >>= 1;
    }
    return newInt;
}

Then remove the trailing zeros:

int flipped = flip(n);
/* shift to remove trailing zeroes */
while (!(flipped & 0x0001))
    flipped >>= 1;

To answer your comment about checking to see if the int is a palindrome, just compare the bit-shifted flipped version with the original:

return n == flipped;

I think this one is pretty ineffective. – polkovnikov.ph Jun 14 '14 at 07:29 — polkovnikov.ph, Jun 14 '14 at 07:29

Strip leading zeroes in binary number in C/C++

4 Answers4