Aligning bit pattern by most-significant bit

Question

I want to XOR two numbers as follows:

11001110 and 110

However, I need to align the bit patterns as such:

11001110
11000000

Any ideas how to do this? I imagine some bitwise operation might be needed, although how would I know how many bits to shift by?

*how would I know how many bits to shift by?* That depends on how many bits the input values are. — , May 18 '17 at 11:38
Surely shifting 110 by 8 would create a misalignment. Likewise, How can we know the position of the most significant bit? — M-R, May 18 '17 at 11:39
@MartinRand please show us some more examples. What is the range of the second value (maybe 000 to 111) ? — Jabberwocky, May 18 '17 at 11:45
I don't understand the question. Why can't you simply shift `110` 5 steps to the left? — Lundin, May 18 '17 at 11:49
Voting to close as unclear, because it's impossible to give answer without blind guess. — user694733, May 18 '17 at 12:16
http://stackoverflow.com/questions/9093323/efficient-bitwise-operations-for-counting-bits-or-find-the-rightleft-most-ones — stark, May 18 '17 at 19:37

score 0 · Answer 1 · answered May 18 '17 at 12:36

Here's one attempt, assuming I got the requirements right:

int topbit(unsigned int x)
{
    for (int i = CHAR_BIT * sizeof x - 1; i >= 0; --i)
    {
        if (x & (1u << i))
            return i;
    }
    return -1;
}

unsigned int alignedxor(unsigned int a, unsigned int b)
{
    const int topa = topbit(a);
    const int topb = topbit(b);
    if (topa < 0)
        return b;
    if (topb < 0)
        return a;
    if (topa > topb)
        return a ^ (b << (topa - topb));
    return (a << (topb - topa)) ^ b;
}

int main(void) {
    printf("%x\n", alignedxor(0xce, 6));
    printf("%x\n", alignedxor(6, 0xce));
    return 0;
}

This prints e, twice, which seems correct but that's all the testing I did.

And yes, you can get the index of the topmost 1-bit more efficiently, but who cares? Also used my rich imagination to deal with corner cases (such as one number being 0).

YePhIcK · Answer 2 · 2017-05-18T15:07:46.907

-1

To know how many bits to shift on Windows you can use this MS-specific function: _BitScanReverse or you can implement your own, something along the lines of:

int findFirstSetBit(uint32_t _n)
{
    int idx = 31;
    for( ; idx >= 0; --idx){
        if(_n & (1 << idx) != 0){
            return idx;
        }
    }
    return -1;
}

edited May 18 '17 at 15:07

answered May 18 '17 at 11:46

YePhIcK

5,816
2
27
52

Also [`__builtin_clz`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fclz) for GCC. – Quentin May 18 '17 at 11:51
Or use posix 2001 ffs. – dbrank0 May 18 '17 at 11:51
Shouldn't idx = 32, so we start at the 31st bit? – M-R May 18 '17 at 11:54
Your function uses a reserved name! – too honest for this site May 18 '17 at 12:15
@Olaf which reserved name would that be? If you are thinking of the `_n` then I must disagree as such a name would only be reserved if it was in global namespace (which it is not in this case). At least according to the language standard. – YePhIcK Jun 12 '18 at 15:37
You know there is a revision history, do you? Check timestamps. Names starting wit underscore are reserved for file-scope. Not just for global names with external linkage (which does not matter here, as the function has external linkage anyway) – too honest for this site Jun 12 '18 at 18:16
Ah, I see it now. My apologies. You are correct (and it was so long ago I totally forgot it was edited and neglected to check now) – YePhIcK Jun 12 '18 at 18:18
Btw: name spaces are something completely different and not related here. It's about scope. http://port70.net/~nsz/c/c11/n1570.html#6.2.3 – too honest for this site Jun 12 '18 at 18:20

Aligning bit pattern by most-significant bit

2 Answers2