Which reminds me of another bit-parallel logical op question arising from study of the Hardin tiling: given two m-bit words (m < 32 say), return 1 (true) just when the 2 x m matrix with those rows contains no 2 x 2 sub-square from set 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 It's not difficult to cobble up a rather messy constant-time solution in C ; I wonder is there something more elegant and less obvious? Fred Lunnon On 1/14/14, Tom Rokicki <rokicki@gmail.com> wrote:
Very nice! My solution was also four ops (discounting the !!), but yours is more elegant and doesn't require common-subexpression elimination.
Yours:
(a-b)&(b-a)&b
Mine:
(a^b)&-(a^b)&b
Now what possible use could this be?
-tom
On Tue, Jan 14, 2014 at 3:33 PM, Mike Speciner <ms@alum.mit.edu> wrote:
I don't know if this is the fastest but, ...
On 2014-01-14 16:26, Tom Rokicki wrote:
For an unsigned 64-bit integer, define br(x) to be the "bit reversal" of x: bit positions 0 and 63 are swapped, 1 and 62 are swapped, and so on.
What's the fastest way in generic C code to compute
br(a) < br(b)
[Don't spoil this if you've seen it already, please.]
-tom
. . . . . . . . .
!!((a-b)&(b-a)&b)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun