Implementing Logical Right Shift in C

Question

I'm working on making a logical right shift function in C using only bitwise operators. Here's what I have:

int logical_right_shift(int x, int n)
{
    int size = sizeof(int); // size of int
    // arithmetic shifts to create logical shift, return 1 for true
    return (x >> n) & ~(((x >> (size << 3) - 1) << (size << 3) -1)) >> (n-1);
}

This actually works for all cases except if n = 0. I've been trying to figure out a way to fix it so it will work for n = 0 as well, but I'm stuck.

Solution 1

int lsr(int x, int n)
{
  return (int)((unsigned int)x >> n);
}

Solution 2

This is what you need:

int logical_right_shift(int x, int n)
{
    int size = sizeof(int) * 8; // usually sizeof(int) is 4 bytes (32 bits)
    return (x >> n) & ~(((0x1 << size) >> n) << 1);
}

Explain

x >> n shifts n bits right. However, if x is negative, the sign bit (left-most bit) will be copied to its right, for example:

Assume every int is 32 bits here, let
x　　　　 =　-2147483648　(10000000 00000000 00000000 00000000), then
x　>>　1　=　-1073741824　(11000000 00000000 00000000 00000000)
x　>>　2　=　-536870912　 (11100000 00000000 00000000 00000000)
and so on.

So we need to erase out those sign extra sign bits when n is negative.

Assume n = 5 here:

0x1 << size moves 1 to the left-most position:

(10000000 00000000 00000000 00000000)

((0x1 << size) >> n) << 1 copies 1 to its n-1 neighbors:

(11111000 00000000 00000000 00000000)

~((0x1 << size) >> n) << 1! reverses all bits:

(00000111 11111111 11111111 11111111)

so we finally obtain a mask to extract what really need from x >> n:

(x >> n) & ~(((0x1 << size) >> n) << 1)

the & operation does the trick.

And the total cost of this function is 6 operations.

Solution 3

Just store your int in an unsigned int, and perform >> upon it.

(The sign is not extended or preserved if you use unsigned int)

http://en.wikipedia.org/wiki/Logical_shift

Solution 4

I think problem is in your ">> (n-1)" part. If n is 0 then left part will be shift by -1. So,here is my solution

int logical_right_shift(int x, int n)
{
  int mask = ~(-1 << n) << (32 - n);
  return  ~mask & ( (x >> n) | mask); 
}

Solution 5

Derived from php's implementation of logical right shifting

function logical_right_shift( i , shift ) {
    if( i & 2147483648 ) {
        return ( i >> shift ) ^ ( 2147483648 >> ( shift - 1 ) );
    }
    return i >> shift;
}

For 32bit platforms only.

View more solutions

Comments

[Ignacio Vazquez-Abrams]

You're making a logical right shift operator for a signed type?

[R.. GitHub STOP HELPING ICE]

This is the correct answer (modulo the unnecessary and ugly cast on the result). Right-shift of a negative value has implementation-defined behavior (or is it an implementation-defined value? I forget), so any implementation of your lsr function in terms of using the >> operator on a signed value is simply non-portable.

[R.. GitHub STOP HELPING ICE]

One issue with this solution: strictly speaking, it has implementation-defined behavior in the case of n==0, since casting from an int to unsigned and back results in implementation defined behavior if the original value is negative. The first conversion must happen modulo UINT_MAX+1, but the conversion back to signed int might simply be a reinterpretation of the representation, in which case the value would be changed.

[Timothy Leung]

I think this is correct. But can you do left shift by 32 times? That will be an undefined shift?

[modulitos]

Yes, if int is, for example, 4 bytes, this fails. He needs to subtract 1 from size so that if int is 4 bytes, sizeis 31.

[Admin]

Please add more information to explain your answer. Code-only answers are not well accepted here.

[MD XF]

@MarkYisri Ironic since the top voted answer on this "thread" is code-only and perfectly, clearly, answers the question.

[M.M]

This causes undefined behaviour if x >> 31 results in a non-zero value

[Jonguo]

@R.. Hi, can you give a example, or a snippet code, that can helps me to understand what you mean ? Thank you.

[radfast]

It's an elegant solution as it involve no conditional statements, therefore no CPU branching. The final | mask operation is unnecessary, as every bit set to 1 by that OR operation will be set to 0 by the AND operation. The mask calculation could be simplified as follows: int mask = int.MinValue >> (n - 1); but my simplification will produce an incorrect result if n == 0, so it depends on your use case - this simplification would not be suitable for a library.