How to determine which bit is set

Question

I have two bytes, they only differ in 1 bit. I want to know what bit this is.

So:

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

Any suggestions are very welcome!!

Thanks,

Erik

Answer 1

If they differ by one bit, xor should give you just that bit. So then you could shift to find which?

Perhaps needs some optimisation:

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 2

The correct solution would be to do

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

Although of course this leaves open the question of what happens if for any reason more than one bit is different.

You could use

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

to get you the index of the highest different bit, if more than one differ.

Warning: For correctness, any such function should also check that the two arguments a and b are actually different before trying to provide a result. Otherwise you 'll get either a meaningless result or an outright exception. This is true of all the solutions presented here, including this one.

Answer 3

You can do this quite easily:

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

Update: fixed...

Answer 4

If you can count from zero, then Math.Log(a^b,2) does the job

Answer 5

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 6

Couldn't resist to write a LINQish version:

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));
}

Update

Due to the fact that the Zip operator is not a default in LINQ, you can get the implementation from Eric out of his blog.

Answer 7

Others have observed that where two bytes differ in only one bit, an XOR operation will return a byte in which just that bit is set. But no one has yet suggested what to me is the obvious next step for establishing which bit that is:

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");
    }
}

I bet the compiler / JITter will make this a nice compact jump lookup table, or something along those lines.