Бит-скручивание для проверки того, находится ли число в определенном диапазоне

Я нашел несколько интересных "source\common\unicode\utf.h" файле "source\common\unicode\utf.h" библиотеки ICU (International Components for Unicode). Битовое чередование предназначено для проверки, находится ли число в определенном диапазоне.

// Is a code point in a range of U+d800..U+dbff?
#define U_IS_LEAD(c) (((c)&0xfffffc00)==0xd800)

Я понял, магическое число (0xfffffc00) происходит из:

MagicNumber = 0xffffffff - (HighBound - LowBound)

Тем не менее, я также обнаружил, что формула не распространяется на любой произвольный диапазон. Кто-нибудь здесь знает, при каких обстоятельствах работает формула?

Есть ли еще один бит для проверки, находится ли число в определенном диапазоне?

Ответы

Ответ 1

Чтобы эти трюки применялись, номера должны иметь некоторые общие функции в их двоичном представлении.

0xD800 == 0b1101_1000_0000_0000
0xDBFF == 0b1101_1011_1111_1111

В действительности этот тест состоит в том, чтобы замаскировать нижние десять бит. Обычно это записывается как

onlyHighBits = x & ~0x03FF

После этой операции ( "а не" ) младшие десять бит onlyHighBits гарантированно будут равны нулю. Это означает, что если это число равно нижнему диапазону интервала, то оно было где-то в интервале раньше.

Этот трюк работает во всех случаях, когда нижний и верхний предел интервала начинаются с одних и тех же цифр в двоичном формате, а в какой-то момент нижний предел имеет только нули, а верхний предел - только один. В вашем примере это находится на десятой позиции справа.

Ответ 2

Если у вас нет границ типа 2 ^ x, вы можете использовать следующий трюк:

если x >= 0 и x < N вы можете проверить оба:

  if Longword( x ) < Longword( N ) then ...

Это работает из-за того, что отрицательные числа в подписанных числах соответствуют наибольшим числам в неподписанных типах данных.

Вы можете расширить это (когда проверка диапазона отключена) до:

  if Longword( x - A ) < Longword ( ( B - A ) ) then ...

Теперь у вас есть оба теста (диапазон [ A, B >) в SUB и CMP плюс один Jcc, предполагая (B - A) предварительно рассчитанным.

Я использую только такие оптимизации, когда это действительно необходимо; например, они, как правило, делают ваш код менее удобочитаемым, и он только сокращает несколько тактов за каждый тест.

Примечание для C, как и для языковых читателей: Longword - это 32-битный тип данных Delphi без знака.

Ответ 3

Формула работает всякий раз, когда диапазон, который вы ищете, начинается с кратного мощности 2 (то есть 1 или более бит на нижнем конце двоичной формы номера заканчивается на 0) и размер диапазон составляет 2 ^ n-1 (то есть низкий и высокий = низкий и низкий | высокий высокий).