Wed, 27 Nov 2002 15:07:31 +0200 (EET) Helger Lipmaa <helger@tcs.hut.fi> I am sure the next problem has been solved a long time ago, but it is hard to find any references. Does anybody know a solution or references? (We came up with a fast algorithm for it ourselves, but inventing wheel is not always the best thing.) Problem: Given nonnegative integers A, B, C. Find the cardinality of {(X,Y):0 <=X < A,0 <= Y < B, 0 <= (X xor Y) < C} where XOR denotes the bitwise XOR of X and Y. Don't know of any references or solution, but, without thinking too carefully, and assuming w.l.o.g. that A>=B, then if A > C then isn't the cardinality simply B*C? That's an upper bound even if A <= C, but I'd have to think more carefully about the exact answer when A < C.