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