Few weeks ago I converted a little function from C language to Delphi. I kept getting completely wrong results all the time even though I was sure the C to Pascal conversion was right (it was really just few lines). After some desperate time, I just tried replacing SHR operator by normal DIV (as A SHR 1 = A DIV 2 and so on). To my surprise, I immediately got the right results. Can Delphi's (I didn't test it in Free Pascal) SHR operator behave differently than C's >> operator?
It does in fact. SHR treats its first operand as unsigned value even though it is a variable of signed type whereas >> takes the sign bit into account. In the function I converted the operand for right shift was often negative and Delphi's SHR just ignored the value of the sign bit.
A Bit of Code
int a, b1, b2; a = -512; b1 = a >> 1; b2 = a / 2;
After running this C code both b1 and b2 have a value of -256.
var A, B1, B2: Integer; A := -512; B1 := A shr 1; B2 := A div 2;
This Delphi code however yields different result: B2 is -256 as expected but B1 has a value of 2147483392.
A Bit of Assembler
Assembler output of C code:
Unit1.cpp.22: b1 = a >> 1; mov eax,[ebp-$0c] sar eax,1 mov [ebp-$10],eax Unit1.cpp.23: b2 = a / 2; mov edx,[ebp-$0c] sar edx,1 jns $00401bb9 adc edx,$00 mov [ebp-$14],edx
Assembler output of Delphi code:
Unit1.pas.371: B1 := A shr 1; mov eax,[ebp-$0c] shr eax,1 mov [ebp-$1c],eax Unit1.pas.373: B2 := A div 2; mov eax,[ebp-$0c] sar eax,1 jns $00565315 adc eax,$00 mov [ebp-$20],eax
As you can see, asm output of C and Delphi divisions is identical. What differs is asm for shift right operator. Delphi uses shr instruction whereas C uses sar instruction. The difference: shr does logical shift and sar does arithmetic one.
The SHR instruction clears the most significant bit (see Figure 6-7 in the Intel Architecture Software Developer's Manual, Volume 1); the SAR instruction sets or clears the most significant bit to correspond to the sign (most significant bit) of the original value in the destination operand.
Quoted from: http://faydoc.tripod.com/cpu/shr.htm
Pingback: In Delphi SHR is a SHR; « The Wiert Corner – irregular stream of Wiert stuff
Thank you for enlightening me :).
Now i understand that ASR is same DIV in Delphi.
Asr is equivalent to Shr for positive numbers.
In case of negative numbers, for example, for value with 32 bits length (integer in Delphi) and shift value 3:
signBit := (Value shr 31);
Shift := 3;
Asrpart := (signBit shl Shift – 1); {1 shl 3 – 1 = 1000b – 1 = 111b}
Result := Asrpart or (Value shr Shift);
{111b + 000(Result)b}
Basicly ASR copies significant bit to bits 30, 29, …. which is depends of shift value. In case of 3, bit_30 and bits_29 filled with copy of bit_31(significant bit), and the rest of the bits filled with result of Shr.
http://en.wikipedia.org/wiki/Arithmetic_shift
function asr(x, y : integer): integer;
begin
result := x div (1 shl y);
end;
Adapting Goa’s solution for negative numbers:
function SAR(a, b : int64): int64;
begin
result := a div (1 shl b);
end;
div is not correct