A Bit of Background
The exterior algebra is a central object in topology and physics (for the physics concept cf. fermion). The basic rule dictating the behavior of the exterior algebra is that \$yx = -xy\$ (and consequently \$x^2 = -x^2 = 0\$). Applying this rule twice we see that \$yzx = -yxz = xyz\$.
The product of two monomials is 0 if any repeated variable occurs, e.g. \$vxyz * stuv = 0\$ because \$v\$ is repeated. Otherwise, we want to put the variables into some standard order, say alphabetical order, and there is a sign introduced that counts how many variables we passed by each other, so for example \$tvy * suxz = +stuvxyz\$ because it takes a total of six crossings to put \$tvysuxz\$ into alphabetical order (on each line I have highlighted the most recently swapped pair): $$tvy * suxz = +\, tvy\;suxz\\ \phantom{tvy * suxz } {}= -tv\mathbf{\large sy}uxz\\ \phantom{tvy * suxz } {}= +t\mathbf{\large sv}yuxz\\ \phantom{tvy * suxz } {}= -\mathbf{\large st}vyuxz\\ \phantom{tvy * suxz } {}= +stv\mathbf{\large uy}xz\\ \phantom{tvy * suxz } {}= -st\mathbf{\large uv}yxz\\ \phantom{tvy * suxz } {}= +stuv\mathbf{\large xy}z\\ $$ Your task will be to compute this sign.
This is a special case of the Koszul Sign Rule which determines the sign of the terms in many sums in math. If you are familiar with determinants, the sign in the determinant formula is an example.
Task
You will take as input two 32 bit integers \$a\$ and \$b\$, which we will interpret as bitflags. You may assume that \$a\$ and \$b\$ have no common bits set, in other words that \$a\mathrel{\&}b = 0\$. Say a pair of integers \$(i, j)\$ where \$0\leq i,j < 32\$ is an "out of order pair in \$(a,b)\$" when:
- \$i < j\$,
- bit \$i\$ is set in \$b\$, and
- bit \$j\$ is set in \$a\$.
Your goal is to determine whether the number of out of order pairs in \$(a,b)\$ is even or odd. You should output true
if the number of out of order pairs is odd, false
if it is even.
A pair of 32 bit integers. If you would like your input instead to be a list of 0's and 1's or the list of bits set in each integer, that's fine.
Outputtrue
or any truthy value if the number of out of order pairs is odd, false
or any falsey value if it is even.
Alternatively, it is fine to output any pair of distinct values for the two cases.
It is also fine to output any falsey value when the number of out of order pairs is odd and any truthy value when the number of out of order pairs is even.
Metric
This is code golf so shortest code in bytes wins.
Test cases
a = 0b000000
b = 0b101101
output = false // If one number is 0, the output is always false.
a = 0b11
b = 0b10
output = UNDEFINED // a & b != 0 so the behavior is unspecified.
a = 0b01
b = 0b10
output = true // 1 out of order pair (1,2). 1 is odd.
a = 0b011
b = 0b100
output = false // 2 out of order pairs (1,2) and (1,3). 2 is even.
a = 0b0101
b = 0b1010
output = true // 3 out of order pairs (1,2), (1,4), (3,4). 3 is odd.
a = 0b0101010 // The example from the introduction
b = 0b1010101
output = false // 6 out of order pairs (1,2), (1,4), (1,6), (3,4), (3,6), (5,6).
a = 33957418
b = 135299136
output = false
a = 2149811776
b = 1293180930
output = false
a = 101843025
b = 2147562240
output = false
a = 1174713364
b = 2154431232
output = true
a = 2289372170
b = 637559376
output = false
a = 2927666276
b = 17825795
output = true
a = 1962983666
b = 2147814409
output = true
// Some asymmetric cases:
a = 2214669314
b = 1804730945
output = true
a = 1804730945
b = 2214669314
output = false
a = 285343744
b = 68786674
output = false
a = 68786674
b = 285343744
output = true
a = 847773792
b = 139415
output = false
1
,2
test case, all of the other test cases seem to give the same result with the inputs swapped. Can you make more test cases which give different results when you swap the inputs? \$\endgroup\$