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.

If you wanted to represent,

A -> B. B -> A,

you could easily represent it by matrix multiplication.

But for nonlinear operations like circular bitwise shifts, is there any nice mathematical representation that can be manipulated easily?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

Sure. Multiplication by a permutation matrix will permute the entries of a vector in any fashion, circular bitwise shift among others. For instance... $$ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} = \begin{pmatrix} a_3 \\ a_1 \\ a_2 \end{pmatrix}$$

share|improve this answer
2  
In general, the circular bitwise shift matrix of any size will have 1's on the super diagonal, a 1 in the lower lefthand corner, and 0's elsewhere. –  Austin Mohr Nov 15 '11 at 19:22
1  
Otherwise known as the basic circulant permutation matrix. –  Stuart Nov 17 '11 at 17:09

Assuming you're working with $m$-bit unsigned integers, the left circular shift is $x \to 2 x + (1-2^m)\ {\rm floor}(x/2^{m-1})$

share|improve this answer
    
Could you explain how you derived this? Based on how left circular shift is usually implemented in code, ((x << 1) | (x >> (m - 1))), I can see the $2x$ as being the left shift, but I'm confused how the rest becomes equivalent to the right shift and the bitwise or. $floor(x/2^{m−1})$ will only ever be 0 or 1, since in the m-bit unsigned integers nothing is twice as big as $2^{m−1}$ since it wraps to 0. So we're conditionally deciding whether to add $(1−2^m)$ based on whether our starting value is greater than $2^{m−1}$. But passed that I'm not sure why adding $(1−2^m)$ does the trick. –  Joseph Garvin Oct 16 '12 at 2:55
    
I get that checking for the value being bigger than $2^{m-1}$ is checking whether the high bit is set, and I get that because we did $2x$ not modulo we need to somehow cancel out the 1 that may be in the 33rd bit, and somehow set the least significant bit, but that addition appears to kill two birds with one stone somehow. –  Joseph Garvin Oct 16 '12 at 2:57
    
When the "high bit" was set, we need to subtract $2^m$ (to get rid of the high bit after the left shift) and add $1$ (to put that bit back in the low bit). –  Robert Israel Oct 16 '12 at 5:54
    
I think I get it, it makes more sense to me if the floor is multiplied out so you get $floor(x/2^{m-1}) - 2^mfloor(x/2^{m-1})$. It's a conditional add of 1 to flip the bit in the lowest place if needed, and a conditional subtraction of the $2^m$ if it was needed. It'd be even clearer if we stored $floor(x/2^{m-1})$ in value called 'highbitset' ;) That's nifty. –  Joseph Garvin Oct 16 '12 at 17:29

Yet another representation is to view the bitwise rotation as multiplication by $X$ in the quotient ring $\mathbb F_2[X]/(X^{32}-1)$, for the appropriate value of $32$.

Of course, this ring has little to do with most other aritmetic operations (except that its addition corresponds to bitwise XOR). This lack of a straightforward connection is inherent in the operations, I think. Cryptographers use it deliberately to frustrate attacks such as linear cryptanalysis.

share|improve this answer
    
True, it's not a field. But so what? I didn't claim it was. –  Henning Makholm Nov 19 '12 at 12:32

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.