Bit-twiddling

[Tim Peters]

[Lars Marius Garshol]
> I'm translating a numerical algorithm from C to Python, but have run
> into a problem in that the algorithm seems to rely on the fact that
> shifting, addition and multiplication all 'wrap' when the result
> exceeds 32 bits.
>
> Since the Python equivalents do not,

int left shift in Python is end-off and 0-fill and non-complaining (same as
in C); int right shift in Python is sign-extending (and undefined in C for
negative signed ints).  Python int + and * do gripe about overflow.

> does there exist a common workaround for this?

The only easy workaround is to use longs, converting to int only when
necessary or expedient.  C defines unsigned int arithmetic to act "as if"
modulo the wordsize, and that's what long Python arithmetic (followed by
low-bit masking) does.

> For example, I'd like
>
>     mt[0]= seed & 0xffffffff
>     for mti in range(1,n):
>         mt[mti]=(69069 * mt[mti-1]) & 0xffffffff
>
> to never put anything that doesn't fit in an unsigned long in the mt
> list.

Provided that seed was a long to begin with, this code almost works as is.
You just need to append "L" to the literals (for 69069 that isn't necessary,
it just avoids the repeated expense of runtime widening; for 0xffffffff it
*is* necessary on a 32-bit machine, else 0xffffffff == -1 gets widened
to -1L and then the masking doesn't accomplish anything (i & -1L == i for
all long i)).

The elements of mt are then all longs, but each one's *value* fits in a
32-bit C unsigned long:  numerically, it computes the same values as would
the C code.

if-you're-really-after-random-numbers-see-ivan-frohne-ly y'rs  - tim