CODEWITHSUNDEEP
cbit-manipulation
Dan
Dan

Reputation: 181

Implementing Logical Right Shift in C

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.

Upvotes: 18

Views: 68701

Answers (8)

Toch
Toch

Reputation: 7

int logicalShift(int x, int n) {
  int mask = x>>31<<31>>(n)<<1;
  return mask^(x>>n);
}

Only for 32 bits

Upvotes: -1

modulitos
modulitos

Reputation: 15854

Milnex's answer is great and has an awesome explanation, but the implementation unfortunately fails due to the shift by total size. Here is a working version:

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

To have 1 as the most significant bit, and all zeroes elsewhere, we need to shift 0x1 by number of bits - 1. I am submitting my own answer because my edit to the accepted answer was somehow rejected.

Upvotes: 1

mingyc
mingyc

Reputation: 536

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.

Upvotes: 17

Ghulam Murtaza
Ghulam Murtaza

Reputation: 21

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.

Upvotes: 2

Levenson
Levenson

Reputation: 73

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); 
}

Upvotes: 3

Jeremiah Willcock
Jeremiah Willcock

Reputation: 30999

As with @Ignacio's comment, I don't know why you would want to do this (without just doing a cast to unsigned like in the other answers), but what about (assuming two's complement and binary, and that signed shifts are arithmetic):

(x >> n) + ((1 << (sizeof(int) * CHAR_BIT - n - 1)) << 1)

or:

(x >> n) ^ ((INT_MIN >> n) << 1)

Upvotes: 0

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 799450

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

Upvotes: 36

Bernd Elkemann
Bernd Elkemann

Reputation: 23560

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

Upvotes: 6

Related Questions