Как определить, какой бит установлен

Question

У меня есть два байта, они отличаются только на 1 бит.Я хочу знать, что это за бит.

Итак:

byte a,b;
a=0;
b=2;

ChangedBit(a,b) should give bit 1
ChangedBit(4,5) should give bit 0
ChangedBit(7,3) should give bit 2

Любые предложения приветствуются !!

Спасибо,

Эрик

Answer 1

Правильным решением было бы сделать

var bit = Math.Log(a ^ b, 2);

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

Вы можете использовать

var bit = (int)Math.Log(a ^ b, 2);

, чтобы получить индекс старшего другого бита, если различается более одного.

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

Answer 2

Если они отличаются на один бит, xor должен дать вам просто этот бит. Итак, вы могли бы перейти, чтобы найти какой?

Возможно, нужна некоторая оптимизация:

static int ChangedBit(int x, int y)
{
    uint bits = (uint)(x ^ y); // need uint to avoid backfill with shift
    int count = -1;
    while (bits != 0)
    {
        count++;
        bits >>= 1;
    }
    return count;        
}

Answer 3

Не удержался от написания версии LINQish:

var firstBits = new BitArray(new byte[] { 3 });
var secondBits = new BitArray(new byte[] { 17 });

var lhs = firstBits.Cast<bool>().Select((b, i) => new { Bit = b, Index = i });
var rhs = secondBits.Cast<bool>().Select((b, i) => new { Bit = b, Index = i });

var differs = lhs.Zip(rhs, (l, r) => new { Left = l, Right = r })
                 .Where(zipped => zipped.Left.Bit != zipped.Right.Bit)
                 .Select(zipped => new { Index = zipped.Left.Index, LeftBit = zipped.Left.Bit, RightBit = zipped.Right.Bit });

foreach (var diff in differs)
{
    Console.WriteLine(String.Format("Differs in bit {0}:", diff.Index));
    Console.WriteLine(String.Format("   First is set to  {0}", diff.LeftBit));
    Console.WriteLine(String.Format("   Second is set to {0}", diff.RightBit));
}

Обновление

Поскольку оператор Zip не является значением по умолчанию в LINQ, вы можете получить реализацию изЭрик из своего блога .

Answer 4

var dif = a ^ b;
int bitNumber = 0;
while (dif != 0 && ((dif & 1) == 0)
{
   dif = dif >> 1;
   ++bitNumber;
}
// bitNumber now contains the zero relative bit that is different.

Answer 5

Если вы можете считать с нуля, то Math.Log(a^b,2) делает работу

Answer 6

Вы можете сделать это довольно легко:

Math.Log(Math.Abs(a-b), 2)

Обновление: исправлено ...

Answer 7

Другие заметили, что если два байта отличаются только одним битом, операция XOR вернет байт, в котором установлен только этот бит.Но никто еще не предположил, что для меня является очевидным следующим шагом для определения того, какой бит:

public static int WhichBitDiffers(byte a, byte b)
{
    var xor = a ^ b;

    switch(xor)
    {
        case 0x80:
            return 7;
        case 0x40:
            return 6;
        case 0x20:
            return 5;
        case 0x10:
            return 4;
        case 0x8:
            return 3;
        case 0x4:
            return 2;
        case 0x2:
            return 1;
        case 0x1:
            return 0;
        default:
            throw new ArgumentException(
                "Values do not differ in exactly one bit");
    }
}

Бьюсь об заклад, компилятор / JITter сделает эту красивую компактную таблицу поиска прыжков, или что-то подобноелинии.