Here is a little puzzle. I encourage not spelunking around for the answer on the Internet. ;) Given a 32-bit unsigned integer x, and a positive integer n, let a = XOR(x, RIGHTSHIFT(x, n)) or in C syntax a = x ^ (x >> n) find, if one exists, a function f such that f(a) = x. In other words, invert the operation on x, or show otherwise. Cheers, Robert
Cute. "32-bit" is completely unnecessary. def f(x,n) : return x^(x>>n); def g(x,n) : while x>>n : x ^= x>>n; n*=2; return x; On 30-Aug-13 20:08, quad wrote:
Here is a little puzzle. I encourage not spelunking around for the answer on the Internet. ;)
Given a 32-bit unsigned integer x, and a positive integer n, let
a = XOR(x, RIGHTSHIFT(x, n))
or in C syntax
a = x ^ (x >> n)
find, if one exists, a function f such that f(a) = x. In other words, invert the operation on x, or show otherwise.
Cheers,
Robert
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 31/08/2013 12:58, Mike Speciner wrote:
def f(x,n) : return x^(x>>n);
def g(x,n) : while x>>n : x ^= x>>n; n*=2; return x;
[quad:]
Given a 32-bit unsigned integer x, and a positive integer n, let ... a = x ^ (x >> n)
find, if one exists, a function f such that f(a) = x. In other words, invert the operation on x, or show otherwise.
It may be worth observing that (modulo implementation details) Mike's solution (*the* solution) is essentially the same thing as 1 / (1+x^n) = 1 - x^n + x^2n - x^3n ..., where (mod 2) minus equals plus. -- g
* Gareth McCaughan <gareth.mccaughan@pobox.com> [Sep 01. 2013 08:03]:
On 31/08/2013 12:58, Mike Speciner wrote:
def f(x,n) : return x^(x>>n);
def g(x,n) : while x>>n : x ^= x>>n; n*=2; return x;
[quad:]
Given a 32-bit unsigned integer x, and a positive integer n, let ... a = x ^ (x >> n)
find, if one exists, a function f such that f(a) = x. In other words, invert the operation on x, or show otherwise.
It may be worth observing that (modulo implementation details) Mike's solution (*the* solution) is essentially the same thing as 1 / (1+x^n) = 1 - x^n + x^2n - x^3n ..., where (mod 2) minus equals plus.
-- g
[...]
The code (note the n*=2; ) rather uses 1/(1-z) = (1+z) * (1+z^2) * (1+z^4) * (1+z^8) * ... where z = x^n Best, jj
On 01/09/2013 17:28, Joerg Arndt wrote: [me:]
It may be worth observing that (modulo implementation details) Mike's solution (*the* solution) is essentially the same thing as 1 / (1+x^n) = 1 - x^n + x^2n - x^3n ..., where (mod 2) minus equals plus.
[Joerg:]
The code (note the n*=2; ) rather uses 1/(1-z) = (1+z) * (1+z^2) * (1+z^4) * (1+z^8) * ... where z = x^n
I see that as an implementation detail -- though really I suppose it's not much more obvious that 1+x+x^2+x^3+... = (1+x)(1+x^2)(1+x^4)... than that 1+x+x^2+x^3+... = 1/(1-x). -- g
On today's pipelined processors, the fastest algorithm is probably some blending of the two. On Sep 1, 2013 4:46 PM, "Gareth McCaughan" <gareth.mccaughan@pobox.com> wrote:
On 01/09/2013 17:28, Joerg Arndt wrote:
[me:]
It may be worth observing that (modulo implementation details)
Mike's solution (*the* solution) is essentially the same thing as 1 / (1+x^n) = 1 - x^n + x^2n - x^3n ..., where (mod 2) minus equals plus.
[Joerg:]
The code (note the n*=2; ) rather uses 1/(1-z) = (1+z) * (1+z^2) * (1+z^4) * (1+z^8) * ... where z = x^n
I see that as an implementation detail -- though really I suppose it's not much more obvious that 1+x+x^2+x^3+... = (1+x)(1+x^2)(1+x^4)... than that 1+x+x^2+x^3+... = 1/(1-x).
-- g
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
participants (5)
-
Gareth McCaughan -
Joerg Arndt -
Mike Speciner -
quad -
Tom Rokicki