How can optimize this boolean function for speed?-CodePudding

I have 2 unsigned 8 bit integers a,b.

The result of the calculation is either -1 or 1.

I work with the binary representation of the integers a,b

a=173;
b=154;
bina = "10101101"
binb = "10011010"

first, the common bits on both integers a XOR b are eliminated:

aANb = a & (a ^ b)
bANa = b & (a ^ b)
aANb = 00100101
bANa = 00010010

For each 1-bit in bANa the number of 1-bits in aANb to the right of the bit are counted.

The sum of the number of bits for each bit in bANa is then calculated.

For example there are 2 1-bits in bANa. The leftmost bit has 2 1-bits to the right of it in aANb:

bANa = 0001  0001
aANb = 0010  0101 -> 2 bits

The second 1-bit in bANa has 1 1-bit to the right of it in aANb:

bANa = 0001001  0
aANb = 0010010  1 -> 1 bit

The sum is then found for these values:

sum = 2 1 = 3

If sum is even, return 1, and if it is odd, return -1

I target x86, but I want it to be open source, so I don't know in which CPU it will run.

I hope it can be speeded up. Notice that if aANb has pairs of contiguous 1, they do not change the result.

Maybe the string of bits can be decomposed in smaller chunks, with tabulated results.

This is my code (is my first ever C# code, I never wrote C# before)

int a = 173;
int b = 154;
int sum = 0;
int aANb = 0;
int bANa = 0;
for (int i = 0; i < 8; i  )
{
    aANb = a & (a ^ b);
    bANa = b & (a ^ b);

    if ((bANa >> i) % 2 == 1)
    {
        for (int j = i; j < 8; j  )
        {
            sum  = (aANb >> j) % 2;
        }
    }
}
int[] answer = { 1, -1 };
string result = $"a={a}\n"  
                $"b={b}\n"  
                $"binary a={Convert.ToString(a, 2).PadLeft(8, '0')}\n"  
                $"binary b={Convert.ToString(b, 2).PadLeft(8, '0')}\n"  
                $"    aANb={Convert.ToString(aANb,2).PadLeft(8, '0')}\n"  
                $"    bANa={Convert.ToString(bANa,2).PadLeft(8, '0')}\n"  
                $"sum={sum}\n"  
                $"result={answer[sum % 2]}";
System.Console.WriteLine(result);

This should output

a = 173
b = 154
binary a=10101101
binary b=10011010
    aANb=00100101
    bANa=00010010
sum=3
result=-1
>>>result=-1

CodePudding user response：

First: aANb and bANa need to be calculated only once outside of the loop.

Second: you don't have to calculate the sum since adding an odd number to sum will invert the "odd" state you can use only an XOR operation:

int a = 173;
int b = 154;
int odd = 0;
int aANb =  a & ~b;
int bANa = b & ~a;
for (int i = 0; i < 8; i  )
{
    if ((bANa >> i) % 2 == 1)
    {
        for (int j = i; j < 8; j  )
        {
            odd ^= (bANa >> j) ; 
        }
    }
}

result:

$"result={answer[odd%2]}";