1 Sep
2013
1 Sep
'13
10:29 a.m.
* 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