CODEWITHSUNDEEP
bit-manipulationshift
Cedric Mamo
Cedric Mamo

Reputation: 1754

Implementing logical shifts

I need to implement a bitwise shift (logical, not arithmetic) on OpenInsight 8.

In the system mostly everything is a string but there are 4 functions that treat numbers as 32-bit integers. The bitwise functions available are AND, OR, NOT and XOR. Any arithmetic operators treat the number as signed.

I'm currently having a problem with implementing left and right shifts which I need to implement SHA-1.

Can anyone suggest an algorithm which can help me accomplish this? Pseudocode is good enough, I just need a general idea.

Upvotes: 0

Views: 262

Answers (3)

phuclv
phuclv

Reputation: 41992

If there's no logical right shift you can easily achieve that by right shifting arithmetically n bits then clear the top n bits

For example: shift right 2 bits:

x >= 2;
x &= 0x3fffffff;

Shift right n bits

x >= n;
x &= ~(0xffffffff << (32 - n));
// or
x >= n;
x &= (1 << (32 - n)) - 1;

For left shifting there's no logical/mathematical differentiation because they are all the same, just shift 0s in.

Upvotes: 0

martinwguy
martinwguy

Reputation: 972

logical shift down by one bit using signed arithmetic and bitwise ops 

if v < 0 then
   v = v & 0x7fffffff   // clear the top bit
   v = v / 2            // shift the rest down
   v = v + 0x40000000   // set the penultimate bit
else
   v = v / 2
fi

Upvotes: 0

Bart Friederichs
Bart Friederichs

Reputation: 33573

You can implement shifting with integer multiplication and division:

Shift left = *2

Shift right = /2

Perhaps you need to mask the number first to make the most siginificant bit zero to prevent integer overflow.

Upvotes: 1

Related Questions