Есть ли дешевый способ "зеркального отражения" битов в байте?

Question

При попытке проверить достижимость по прямой линии без зацикливания, вы можете использовать представление в виде битборда. Представьте себе шахматы, строку или столбец доски, представленные в виде байта, и вопрос, может ли ладья на квадрате X захватить цель на квадрате T.

Пусть T: Target, X: Start, O: другие занятые квадраты, _: пустой квадрат

Я счел удобным визуализировать возможные сценарии, используя следующие символы:

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

Здесь есть 4 случая интереса - помечены из AD. Случаи A и B просты в обращении.

Но случаи C и D - нет. Вы не можете просто проверить наличие> или <, чтобы выяснить, достижима ли цель или заблокирован ли путь.

Что можно сделать, однако, это преобразовать C,D в A,B, отражая биты в байте. Итак, бит 0 -> бит 7, бит 1 -> бит 6, ...

Кто-нибудь знает, есть ли оптимизированная реализация для этого переключения?

РЕДАКТИРОВАТЬ: Я только что заметил, что другой случай: E: OT__X___ ... моя теория не работает, но вопрос остается.:)

Answer 1

Вместо

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

Кажется логичным обратить X и T в случаях C и D:

//C: __OTO_X_ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//D: __OOT_X_ -> Target left of X, X leftmost    -> T > X and O < X -> reachable

Я понимаю, что если Т был епископом, а Х был ладьей, то Т не мог бы двигаться так, как может Х, но все, что мы делаем, это проверяем, была ли Т ладья, если бы он мог перейти к Х. Ответ на этот вопрос тот же. как X движется к T. Либо может, либо не может, что отвечает противоположному (может ли X перейти к T).

Answer 2

Вы можете сделать этот тест без реверса. Если x, t, а также o являются битовые маски, как в вашем примере (где x а также t установить ровно один бит, и эти биты не установлены в o), то вы можете создать битовую маску, содержащую биты между t а также x следующее:

tx = t | x
txhi = tx & (tx - 1)
return (txhi - 1) ^ (tx - 1)

При этом используется вычитание 1, которое заменяет битовую комбинацию, заканчивающуюся на "100...000", на "011...111". Затем вы можете просто проверить, пересекается ли эта маска с o,

Answer 3

Для этого есть несколько решений для хакерских атак (один из примеров приведен ниже), но если вы когда-либо имеете дело только с одним байтом, простая таблица поиска из 256 записей, вероятно, является наиболее эффективной.

Вот пример из моей личной библиотеки кодов из моих хакерских дней FFT (не гарантируя, что это соответствует современным стандартам C или чему-то еще - в частности, uint8 это typedef за unsigned char, но современный клиент, IIRC, родной uint8_t что послужит цели)

inline uint8 bitrev8(uint8 n)
{ uint8 tmp = 0x55;
  n = (((n >> 1) & tmp) | ((n & tmp) << 1));

  tmp = 0x33;
  n = (((n >> 2) & tmp) | ((n & tmp) << 2));

  return ((n >> 4) | (n << 4));
}

Из-за непрактичности больших справочных таблиц соответствующие подпрограммы для 16-, 32- и 64-битных данных являются гораздо большим преимуществом, чем 8-битная версия, которая, очевидно, разрешает гораздо больше команд, чем простая v = reversed[n]; было бы...

Answer 4

Создайте 256-байтовую таблицу поиска для каждого байта и используйте ее вместо выполнения каких-либо вычислений.