How to determine which bit is set

Question

I have two bytes, they differ only 1 bit. I want to know what it 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,

Eric

Answer 1

The right decision would be to make

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

Although, of course, this leaves open the question of what will happen if, for whatever reason, more than one bit is different.

you can use

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

to get the index of the highest different bits, if slightly different.

Caution: For correctness, any such function should also verify that the two arguments a and b are actually different before attempting to provide a result. Otherwise, you will get either a meaningless result, or just an exception. This applies to all solutions presented here, including this one.

Answer 2

If they differ by one bit, xor should only give you that bit. So you can go to find that?

Optimization may be required:

 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

You can do this quite easily:

 Math.Log(Math.Abs(ab), 2) 

Update: fixed ...

Answer 4

If you can count from scratch, 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

Failed to refrain from writing 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 standard in LINQ, you can get the implementation from Eric from your blog .

Answer 7

Others have noticed that when two bytes differ in only one bit, the XOR operation returns a byte in which only this bit is set. But no one has yet suggested what is the obvious next step for me to determine which bit 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 / JITter compiler will make this wonderful compact jump search table or something like that.