Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading the source code of a stream cypher (zuc): I cannot understand properly why they define the multiplication by power of 2 in this way:

#define MulByPow2(x, k) (   (   ((x) << k)|((x) >> (31 - k))      & 0x7FFFFFFF)

In the example $x$ is the first term of the product and $k$ is the power of $2$. for who don't understand c here's the translation: * ((x) << k) is the binary left shifting operation by k position. This correspond to the usual multiplication by power of 2. * | is the bitwise OR operator * (x) >> (31 - k) is the opopsite operation of <<. * & 0x7FFFFFFF i think this play the role of mod(2^31-1)

I don't get the meaning of "|((x) >> (31 - k)) " in the multiplication.

Thanks for help. :)

share|improve this question
add comment

1 Answer 1

If you calculate in 64 bits, then $x\ll k$ is $2^kx$. Write this as two 32 bit words as $h\cdot 2^{32}+ (s\cdot 2^{31}+l)$ with high word $h$, low (unsigned) word $l$ und msb $s$. Then $s\equiv 1\pmod{2^{31}-1}$ and $h\cdot 2^{32}\equiv 2h\pmod {2^{31}-1}$. Note that $2h+s$ can be obtained directly by calculating $x\gg (31-k)$. Normally, one should use $+$ instead of $|$, but fortunately the two expressions are always bit-disjoint, provided $x<2^{31}$.

By the way, the macro may be problematic if an expression is fed into $k$. To play safe, each $k$ schould be surrounded by parentheses.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.