vipersassassin vipersassassin - 1 month ago 6
C# Question

How to check if 1 bit is off as compared to the expected number

I am checking a FAT systems table and need to determine if a 32 bit integer is off by one bit as compared to what is expected. Normally the listed location is +1 of the current location, unless a jump is needed due to another file in the way. If the disk is having corruption issues, the value is usually off by 1 bit being set outside of the norm. I have written how I am checking now, but would like to know if there is a simpler or fast manner to perform this function.

internal bool CheckFatValueToIndex(int expectedCluster, int recievedValue)
{
/*Clear one bit and compare to expected value
*Return true if expected cluster is 1 bit off*/
if ((expectedCluster | 0x01) == recievedValue || (expectedCluster | 0x02) == recievedValue || (expectedCluster | 0x04) == recievedValue || (expectedCluster | 0x08) == recievedValue || (expectedCluster | 0x10) == recievedValue || (expectedCluster | 0x20) == recievedValue || (expectedCluster | 0x40) == recievedValue || (expectedCluster | 0x80) == recievedValue || (expectedCluster | 0x100) == recievedValue)
return true;
if ((expectedCluster | 0x200) == recievedValue || (expectedCluster | 0x400) == recievedValue || (expectedCluster | 0x800) == recievedValue || (expectedCluster | 0x1000) == recievedValue || (expectedCluster | 0x2000) == recievedValue || (expectedCluster | 0x4000) == recievedValue || (expectedCluster | 0x8000) == recievedValue)
return true;

return false;
}

Answer

First of all you need to extract changed bits, this can be simply done with XOR:

expectedCluster ^ receivedValue

Each set bit represents a difference: if bits are the same (0 or 1) result is 0 but it's 1 if they differ.

Now you have to count them. You can use Hamming algorithm:

int CountSetBits(int x) {
    int count = 0;
    for (count=0; x; ++count)
        x &= x - 1;

    return count;
}

You can then check it:

return CountSetBits(expectedCluster ^ receivedValue) > 1;

Edit: Quantic suggested to check if XORed number is a power of 2, if you do not need to count how many corrupted/changed bits you have then this should be faster (if you care):

bool IsPowerOf2(int x) {
    return x != 0 && (x & (x - 1)) == 0;
}