Можно ли привести 0x11 к 0x00, сохранив 0x01 -> 0x01 и 0x -> 10, используя только побитовые операции?

Question

Можно ли реализовать функцию, которая приводит к этому отображению:

{
  (0x01, 0x01),
  (0x10, 0x10),
  (0x11, 0x00)
}

Использование только побитовых операций?

Контекст

В инфраструктуре Flixel естьнабор из четырех констант,

FlxObject.LEFT:uint   = 0x0001;
FlxObject.RIGHT:uint  = 0x0010;
FlxObject.UP:uint     = 0x0100;
FlxObject.DOWN:uint   = 0x1000;

Очевидно, предназначен для работы с побитовыми операторами.Я пытался написать функцию, используя только побитовые операторы, которые возвращали бы противоположное направление того, что было передано (в терминах этих констант FlxObject).

Некоторые примеры сопоставлений:

{
    (0x0110, 0x1001),
    (0x0100, 0x1000),
    (0x1010, 0x0101),
    (0x0001, 0x0010),
    (0x1100, 0x0000)
}

Проблема в том, что мое решение имеет тенденцию ломаться, когда вы передаете ему что-то вроде 0x0011, 0x1100, 0x1110 и т. П., И требует проверки в этом случае.Код тестирования здесь (также по адресу http://pastie.org/3420169):

#!/usr/bin/env python

from sys import stdout
from os import linesep

# Implementation without conditional
def horiz(dir):
    return(dir ^ 0x0011 ^ 0x1100) & 0x0011

def vert(dir):
    return (dir ^ 0x1100 ^ 0x0011) & 0x1100

def oppositeDirection(dir):
    return horiz(dir) | vert(dir)


# Implementation with conditional
def horizFix(dir):
    dir = horiz(dir)
    return dir if dir != 0x0011 else 0

def vertFix(dir):
    dir = vert(dir)
    return dir if dir != 0x1100 else 0

def oppositeDirectionFix(dir):
    return horizFix(dir) | vertFix(dir)

failcount = 0
testcount = 0

def test(dir, expect, func):
    global failcount, testcount
    testcount += 1
    result = func(dir)
    stdout.write('Testing: {0:04x} => {1:04x}'.format(dir, result))
    if result != expect:
        stdout.write('\t GOT {0:04x} expected {1:04x}'.format(result, expect))
        failcount += 1
    stdout.write(linesep)

test_cases =[0x0000, 0x0001, 0x0010, 0x0100, 0x1000, 0x0011, 0x0101, 0x1001, 0x0110, 0x1010, 0x1100, 0x0111, 0x1011, 0x1101, 0x1110, 0x1111] 


print 'Testing full oppositeDirection function----------------'
for case in test_cases:
    test(case, oppositeDirectionFix(case), oppositeDirection)

print '\nTesting horiz function---------------------------------'
for case in test_cases:
    test(case, horizFix(case), horiz)

print '\nTesting vert function----------------------------------'
for case in test_cases:
    test(case, vertFix(case), vert)


print '{0}Succeeded: {2}/{1}, Failed: {3}/{1}'.format(linesep, testcount, testcount - failcount, failcount)

Если вы запустите тест, вы увидите, что в случаях, таких как 0x0011 и 0x0000, horiz вернет 0x0011, а для 0x1100 и 0x000 vert вернет 0x1100Так близко!

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

Answer 1

Нет, вам нужно провести какой-то тест, потому что ваш результат зависит от двух соседних битов.

Вы можете использовать XOR с 1111 и затем проверить, содержит ли результат 1100 или 0011.

Но поскольку у вас есть только 16 значений для проверки, не будет ли этопроще сделать функцию переключения / выбора / сопоставления для 8 допустимых значений?

Answer 2

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

Если вы измените определения horiz(), vert() и oppositeDirection() в коде тестирования на следующее:

def horiz(dir):
    return (((dir << 4) & ~dir & 0x0010) | ((dir >> 4) & ~dir & 0x0001))

def vert(dir):
    return (((dir << 4) & ~dir & 0x1000) | ((dir >> 4) & ~dir & 0x1000))

def oppositeDirection(dir):
    return (((dir << 4) & ~dir & 0x1010) | ((dir >> 4) & ~dir & 0x0101))

тогда все тесты пройдены. Если мы посмотрим на horiz() (остальные похожи):

Вторая цифра (справа) задается как:

((dir << 4) & ~dir & 0x0010)

и первая цифра:

((dir >> 4) & ~dir & 0x0001)

Рассматривая далее, как рассчитывается первая цифра, (dir >> 4) возвращает нам исходную вторую цифру, но выровненную с первой. ~dir получает значение, обратное исходной цифре. Затем мы И, и те вместе, и И с маской, чтобы получить только цифру, которую мы вычисляем, чтобы мы не испортили другие цифры.

Итак, если мы назовем исходные цифры A (первая) и B (вторая) и назовем новую первую цифру X, мы получим:

X = ~A & B

Вторая цифра рассчитывается аналогичным образом, смещаясь в другом направлении. Мы также можем комбинировать вычисления горизонтальных и вертикальных бит, просто корректируя маски.