У меня есть вопрос (или, скорее, сообщение об ошибке) о поведении смещения бит в Delphi (проверен в Borland Delphi 7).
Цель: выполнить "арифметическое" побитное смещение вправо с любым числом.
Это означает, что знаковый бит должен быть расширен - двоичный номер будет заполнен слева 1 вместо 0, если был установлен самый старший бит числа.
Итак, число "-1" после правильного арифметического сдвига должно оставаться одним и тем же числом (все биты = 1), но с "логическим сдвигом" (который всегда заполняет число нулями) должно давать максимальное положительное целое число (максимальное положительное целое число со знаком, чтобы быть правильным)
Я тестировал его только на 32-битной системе (Windows); кроме того, мне нужно, чтобы он явно работал с 32-битными целыми числами.
Похоже, что в Delphi есть внутренняя ошибка с "shr" , когда исходный номер хранится в переменной.
Мой пример кода:
program bug;
{$APPTYPE CONSOLE}
var
I:Integer;
C:Cardinal;
begin
I := -1; // we’ll need that later
C := $FFFFFFFF;
(Его только начало). Затем, попробуем попробовать "shr" s:
Writeln('0) ', -1 shr 1 );
Writeln('1) ', $FFFFFFFF shr 1 );
"- 1" является эквивалентом знака "$ FFFFFFFF". Кажется, что поведение "shr" (арифметическое или логическое) основано на том, подписан ли исходный номер или нет (целое или кардинальное).
Выход:
0) -1
1) 2147483647
Совершенно верно. Затем мне нужно попытаться вручную перевести эти числа в целые числа или кардиналы:
Writeln('2) ', Integer(-1) shr 1 );
Writeln('3) ', Integer($FFFFFFFF) shr 1 );
Writeln('4) ', Cardinal(-1) shr 1 );
Writeln('5) ', Cardinal($FFFFFFFF) shr 1 );
Результат:
2) -1
3) -1
4) 2147483647
5) 2147483647
Все еще правильно. Итак, я думаю, что я могу сделать что-либо "целым", если мне нужен арифметический сдвиг; или бросать в "кардинал", когда мне нужен логический сдвиг. Но ждать! Пример с переменными (указанными выше):
Writeln('6) ', I shr 1 );
Writeln('7) ', C shr 1 );
И вдруг:
6) 2147483647
7) 2147483647
НЕПРАВИЛЬНО. Мое "I" было целым числом со знаком, и я ожидал арифметического сдвига! Итак, возможно ли может помочь кастинг?
Writeln('8) ', Integer(I) shr 1 );
Writeln('9) ', Cardinal(I) shr 1 );
Writeln('A) ', Integer(C) shr 1 );
Writeln('B) ', Cardinal(C) shr 1 );
Нет, все тот же...
8) 2147483647
9) 2147483647
A) 2147483647
B) 2147483647
Вещи еще хуже, если я попытаюсь сделать функцию "a shr b" и использовать ее вместо:
// Simple shift right with signed integers
function shrI(a,b:Integer):Integer;
begin
Result := a shr b;
end;
// Simple shift right with unsigned integers
function shrC(a,b:Cardinal):Cardinal;
begin
Result := a shr b;
end;
Сейчас:
Writeln('C) ', shrI(-1,1) );
Writeln('D) ', shrC($FFFFFFFF,1) );
- он переставал работать даже с постоянными выражениями: (это имеет смысл, потому что числа снова хранятся в переменных внутри функции)
C) 2147483647
D) 2147483647
Так как мне все равно нужно сделать правильный арифметический сдвиг, я написал эти формулы для этого (сдвиг "справа" на "бит" ). Во-первых, это логический сдвиг:
(a shr b) and ((1 shl (32-b))-1)
Мне просто нужно поразрядно, а результат с "32 - b" (справа), чтобы очистить "b" левые биты в случае, если "shr" меня не сработает и вместо этого сделал арифметический сдвиг (ни один пример не показывает это, но просто чтобы убедиться). Тогда арифметический сдвиг:
(a shr b) or (( 0-((a shr 31) and 1)) shl (32-b))
Мне нужно поразрядное или результат с "b" слева, но только когда был установлен старший бит; для этого сначала я беру знаковый бит с "(a shr 31) и 1", затем отрицаем это число, чтобы получить "-1" (или $FFFFFFFF - все бит = 1), если источник был отрицательным, и 0 в противном случае (я положил "0-x" вместо "-x", потому что в моем C-порту в некоторых случаях bcc32 C-компилятор сообщает предупреждение о привязке, чтобы отрицать целое число без знака); и, наконец, я переместил его на бит "32 - b", поэтому я получил то, что желаю, даже когда "shr" терпит неудачу и даст нули. Я сделал две версии каждой функции для работы как с целыми числами, так и с кардиналами (также я мог делиться именами и "перегружать" их для меня, но здесь я не сделаю этого, чтобы этот пример был ясным):
// Logical shift right with signed integers
function srlI(a,b:Integer):Integer;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;
// Arithmetic shift right with signed integers
function sraI(a,b:Integer):Integer;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;
// Logical shift right with unsigned integers
function srlC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;
// Arithmetic shift right with unsigned integers
function sraC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;
Проверьте это:
Writeln('E) ', sraI(-1,1) );
Writeln('F) ', srlI(-1,1) );
Writeln('G) ', sraC($FFFFFFFF,1) );
Writeln('H) ', srlC($FFFFFFFF,1) );
И получили отличные результаты:
E) -1
F) 2147483647
G) 4294967295
H) 2147483647
(G-case все еще верен, потому что "4294967295" - это неподписанная версия "-1" )
Окончательные проверки с переменными:
Writeln('K) ', sraI(I,1) );
Writeln('L) ', srlI(I,1) );
Writeln('M) ', sraC(C,1) );
Writeln('N) ', srlC(C,1) );
Perfect:
K) -1
L) 2147483647
M) 4294967295
N) 2147483647
Для этой ошибки я также попытался изменить второе число (количество сдвига) на переменную и/или попробовать различное кастинг - такая же ошибка присутствует, похоже, что она не связана со вторым аргументом. И, пытаясь отличить результат (от целого или от кардинального), до выхода ничего не улучшилось.
Чтобы убедиться, что Im не только тот, у кого есть ошибка, я попытался запустить весь свой пример в http://codeforces.com/ (там есть зарегистрированный пользователь может скомпилировать и выполнить часть кода на разных языках и компиляторах на стороне сервера), чтобы увидеть результат.
"Delphi 7" компилятор дал мне именно то, что у меня есть - ошибка присутствовала. Альтернативный вариант "Free Pascal 2" показывает еще больший неправильный вывод:
0) 9223372036854775807
1) 2147483647
2) 9223372036854775807
3) 9223372036854775807
4) 2147483647
5) 2147483647
6) 2147483647
7) 2147483647
8) 2147483647
9) 2147483647
A) 2147483647
B) 2147483647
C) 2147483647
D) 2147483647
E) -1
F) 2147483647
G) 4294967295
H) 2147483647
K) -1
L) 2147483647
M) 4294967295
N) 2147483647
Странный "9223372036854775807" в случаях 0-2-3 (там были "-1", "Целое число (-1)" и "Целое число ($ FFFFFFFF)", которые не помнят).
Вот мой весь пример в Delphi:
program bug;
{$APPTYPE CONSOLE}
// Simple shift right with signed integers
function shrI(a,b:Integer):Integer;
begin
Result := a shr b;
end;
// Simple shift right with unsigned integers
function shrC(a,b:Cardinal):Cardinal;
begin
Result := a shr b;
end;
// Logical shift right with signed integers
function srlI(a,b:Integer):Integer;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;
// Arithmetic shift right with signed integers
function sraI(a,b:Integer):Integer;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;
// Logical shift right with unsigned integers
function srlC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;
// Arithmetic shift right with unsigned integers
function sraC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;
var
I:Integer;
C:Cardinal;
begin
I := -1;
C := $FFFFFFFF;
Writeln('0) ', -1 shr 1 );
Writeln('1) ', $FFFFFFFF shr 1 );
// 0) -1 - correct
// 1) 2147483647 - correct
Writeln('2) ', Integer(-1) shr 1 );
Writeln('3) ', Integer($FFFFFFFF) shr 1 );
// 2) -1 - correct
// 3) -1 - correct
Writeln('4) ', Cardinal(-1) shr 1 );
Writeln('5) ', Cardinal($FFFFFFFF) shr 1 );
// 4) 2147483647 - correct
// 5) 2147483647 - correct
Writeln('6) ', I shr 1 );
Writeln('7) ', C shr 1 );
// 6) 2147483647 - INCORRECT!
// 7) 2147483647 - correct
Writeln('8) ', Integer(I) shr 1 );
Writeln('9) ', Cardinal(I) shr 1 );
// 8) 2147483647 - INCORRECT!
// 9) 2147483647 - correct
Writeln('A) ', Integer(C) shr 1 );
Writeln('B) ', Cardinal(C) shr 1 );
// A) 2147483647 - INCORRECT!
// B) 2147483647 - correct
Writeln('C) ', shrI(-1,1) );
Writeln('D) ', shrC($FFFFFFFF,1) );
// C) 2147483647 - INCORRECT!
// D) 2147483647 - correct
Writeln('E) ', sraI(-1,1) );
Writeln('F) ', srlI(-1,1) );
// E) -1 - correct
// F) 2147483647 - correct
Writeln('G) ', sraC($FFFFFFFF,1) );
Writeln('H) ', srlC($FFFFFFFF,1) );
// G) 4294967295 - correct
// H) 2147483647 - correct
Writeln('K) ', sraI(I,1) );
Writeln('L) ', srlI(I,1) );
// K) -1 - correct
// L) 2147483647 - correct
Writeln('M) ', sraC(C,1) );
Writeln('N) ', srlC(C,1) );
// M) 4294967295 - correct
// N) 2147483647 - correct
end.
Тогда я был любопытным, эта ошибка также присутствует в С++? Я написал порт на С++ и использую (Borland!) Bcc32.exe для его компиляции.
Результаты:
0) -1
1) 2147483647
2) -1
3) -1
4) 2147483647
5) 2147483647
6) -1
7) 2147483647
8) -1
9) 2147483647
A) -1
B) 2147483647
C) -1
D) 2147483647
E) -1
F) 2147483647
G) 4294967295
H) 2147483647
K) -1
L) 2147483647
M) 4294967295
N) 2147483647
Все в порядке. Вот версия С++, на случай, если кто-то захочет посмотреть:
#include <iostream>
using namespace std;
// Simple shift right with signed integers
int shrI(int a, int b){
return a >> b;
}
// Simple shift right with unsigned integers
unsigned int shrC(unsigned int a, unsigned int b){
return a >> b;
}
// Logical shift right with signed integers
int srlI(int a, int b){
return (a >> b) & ((1 << (32-b))-1);
}
// Arithmetic shift right with signed integers
int sraI(int a, int b){
return (a >> b) | (( 0-((a >> 31) & 1)) << (32-b));
}
// Logical shift right with unsigned integers
unsigned int srlC(unsigned int a, unsigned int b){
return (a >> b) & ((1 << (32-b))-1);
}
// Arithmetic shift right with unsigned integers
unsigned int sraC(unsigned int a, unsigned int b){
return (a >> b) | (( 0-((a >> 31) & 1)) << (32-b));
}
int I;
unsigned int C;
int main(){
I = -1;
C = 0xFFFFFFFF;
cout<<"0) "<<( -1 >> 1 )<<endl;
cout<<"1) "<<( 0xFFFFFFFF >> 1 )<<endl;
// 0) -1 - correct
// 1) 2147483647 - correct
cout<<"2) "<<( ((int)(-1)) >> 1 )<<endl;
cout<<"3) "<<( ((int)(0xFFFFFFFF)) >> 1 )<<endl;
// 2) -1 - correct
// 3) -1 - correct
cout<<"4) "<<( ((unsigned int)(-1)) >> 1 )<<endl;
cout<<"5) "<<( ((unsigned int)(0xFFFFFFFF)) >> 1 )<<endl;
// 4) 2147483647 - correct
// 5) 2147483647 - correct
cout<<"6) "<<( I >> 1 )<<endl;
cout<<"7) "<<( C >> 1 )<<endl;
// 6) -1 - correct
// 7) 2147483647 - correct
cout<<"8) "<<( ((int)(I)) >> 1 )<<endl;
cout<<"9) "<<( ((unsigned int)(I)) >> 1 )<<endl;
// 8) -1 - correct
// 9) 2147483647 - correct
cout<<"A) "<<( ((int)(C)) >> 1 )<<endl;
cout<<"B) "<<( ((unsigned int)(C)) >> 1 )<<endl;
// A) -1 - correct
// B) 2147483647 - correct
cout<<"C) "<<( shrI(-1,1) )<<endl;
cout<<"D) "<<( shrC(0xFFFFFFFF,1) )<<endl;
// C) -1 - correct
// D) 2147483647 - correct
cout<<"E) "<<( sraI(-1,1) )<<endl;
cout<<"F) "<<( srlI(-1,1) )<<endl;
// E) -1 - correct
// F) 2147483647 - correct
cout<<"G) "<<( sraC(0xFFFFFFFF,1) )<<endl;
cout<<"H) "<<( srlC(0xFFFFFFFF,1) )<<endl;
// G) 4294967295 - correct
// H) 2147483647 - correct
cout<<"K) "<<( sraI(I,1) )<<endl;
cout<<"L) "<<( srlI(I,1) )<<endl;
// K) -1 - correct
// L) 2147483647 - correct
cout<<"M) "<<( sraC(C,1) )<<endl;
cout<<"N) "<<( srlC(C,1) )<<endl;
// M) 4294967295 - correct
// N) 2147483647 - correct
}
Перед публикацией здесь я попытался найти эту проблему и не нашел упоминания об этой ошибке. Также я посмотрел здесь: Каково поведение shl и shr для операндов без регистрового размера? и здесь: Арифметический сдвиг Правильно, чем логический сдвиг вправо - но были обсуждены другие проблемы (что компилятор внутренне применяет любой тип к 32-битовому номеру, прежде чем делать фактический сдвиг или перекладывать более 31 бит), но не моя ошибка.
Но подождите, вот моя проблема: http://galfar.vevb.net/wp/2009/shift-right-delphi-vs-c/!
С одним замечанием: говорят -
В Delphi SHR всегда является операцией SHR: он никогда не учитывает знак.
Но мой пример показывает, что Delphi делает принимает знак, но только тогда, когда исходный номер является константным выражением, а не переменной. Таким образом, "-10 shr 2" равно "-3", но "x shr 2" равно "1073741821", когда "x: = - 10".
Итак, я думаю, что это ошибка, а не "поведение", которое "shr" всегда логично. Видите ли, не всегда. Попытка включить/отключить любые параметры компилятора, такие как проверка диапазона или оптимизация, ничего не изменили.
Кроме того, здесь я разместил примеры того, как обойти эту проблему и иметь правильный арифметический сдвиг вправо. И мой главный вопрос: я прав?
Похоже, что левый сдвиг всегда хорош в Delphi (он никогда не использует оригинальный бит знака, а не "undefined": для целых чисел со знаком он ведет себя как кастинг в кардинал перед сдвигом и возвращает результат обратно в целое число - число может внезапно стать отрицательным, конечно). Но теперь мне интересно, есть ли в Delphi другие подобные ошибки? Это первая действительно значительная ошибка, которую я когда-либо обнаружил в Delphi 7. Я люблю Delphi больше, чем С++, потому что я всегда был уверен, что мой код всегда делает то, что я хочу, без отладки тестирования каждого нового необычного фрагмента кода, который Im напишите (IMHO).
P.S. Вот несколько полезных ссылок, которые система StackOverflow предлагает мне, когда я набрал свой заголовок, прежде чем публиковать этот вопрос. Опять же, интересная информация, но не об этой ошибке:
Арифметический бит-сдвиг по целому знаку со знаком
Подписан правильный сдвиг = странный результат?
Операторы побитового смены на подписанных типах
Должны ли вы всегда использовать 'int' для чисел в C, даже если они неотрицательны?
Определены ли результаты побитовых операций с целыми знаками?
Проверка того, что сдвиг вправо/сдвиг C/С++ является арифметическим для конкретного компилятора?
Эмуляция переменной бит-сдвига с использованием только постоянных сдвигов?
P.P.S. Большое спасибо Stack Exchange Team за помощь в публикации этой статьи. Ребята, вы качаете!
