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

Question

В файле "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)

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

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

Answer 1

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

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

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

onlyHighBits = x & ~0x03FF

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

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

Answer 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 без знака.

Answer 3

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