Talk:Circular shift

Terminology

The article says the number of circular shifts of a set of size n is (n − 1)!. Using circular shifts in the sense used in the example, I think the number of circular shifts of a set of size n is n. Ray Spalding 01:31, 29 May 2006 (UTC)

I removed the statement. It does not make sense because we are not talking about sets here. --Spoon! 10:20, 21 January 2007 (UTC)

Number of circular shifts

If we have N elements in set(register,variable,etc) 
e.g. 1 2 3 4 5 6 7 
 left 2 3 4 5 6 7 1, 3 4 5 6 7 1 2, 4 5 6 7 1 2 3, 5 6 7 1 2 3 4,6 7 1 2 3 4 5,7 1 2 3 4 5 6
and right           7 1 2 3 4 5 6, 6 7 1 2 3 4 5,5 6 7 1 2 3 4, 4 5 6 7 1 2 3,3 4 5 6 7 1 2,2 3 4 5 6 7 1
Its clearly seen that Nth rotation to either side(rotation are equivalent) will become the same set.      
So the number of possible rotations is n-1               

—The preceding unsigned comment was added by 84.228.240.173 (talk) 10:41, 11 March 2007 (UTC).

Implementation

Took me awhile to figure out an efficient implementation of this , but you can implement it by ORing x left shifts and (n - x) right shifts. n is the size of your bit pattern. --Voidvector (talk) 04:47, 10 October 2008 (UTC)

Potential Bug

The implementation has a potential bug. When shift == 0, the right half becomes x << 32, which is undefined in C (shift must be strictly less than the width of the word - see section 5.8 in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf). If you're on a IA-32 processor, shifts effectively mask against 31 on the right operand, so x << 32 becomes x << 0, which |'s with x >> 0 to give the right result, but an alternate implementation (say, clamp to [0,31]) might fail. 76.202.198.141 (talk) 07:09, 21 January 2009 (UTC)

Behaviour of right-shift is also undefined in C. May propagate bit 31 right. —Preceding unsigned comment added by 212.44.19.206 (talk) 10:57, 3 March 2009 (UTC)

Thank you. Both of those bugs in the implementation have been fixed now.

• shift=0 and shift=32 are now handled by a special-case if() statement that avoids that undefined behavior.
• "value" has been changed to an unsigned int, so the behavior of right-shifting that value has well-defined behavior in C. See Right-shift operator#Shifts in C, C++, C.23 which says "In C, C++, and C#, computations with the left operand as an unsigned integer use logical shifts."

--DavidCary (talk) 05:31, 20 June 2011 (UTC)

Believe it or not, there's still a potential bug there. The bug is leaking timing information due to two different code paths.

Jeffrey Walton 12:22, 20 February 2013 (UTC)

Yes, I see how this leaks timing information for algorithms that use key-dependent or data-dependent rotation -- block cipher mentions a few.

I suspect that this special-case if() -- whether it is optimized away or not -- does not leak timing information for algorithms that only use hardwired shift amounts -- Cryptomeria cipher, SipHash, Skein, etc.

Is there a way to fix this potential bug in a way that still allows C compilers to recognize that it's actually a circular shift, and to use efficient rotation instructions (when available)?

--DavidCary (talk) 18:38, 28 May 2013 (UTC)

I'm aware that this discussion will not be constructive (Wikipedia's nature!) but what's with the awful piece of code in this article? Why is there an underscore before the function names? Why are you passing const values to the functions?! Ugly piece of code, unnecessarily made un-readable ! congrats to the user who wrote it, I couldn't even if I tried ! It's either out of a 1970's textbook or the work of a "coder" with 1970's mind-set ! 198.72.137.243 (talk) 23:45, 6 October 2013 (UTC)

C function names with leading underscore are reserved and should not be used in user code, therefore I removed that underscore. The const attribute is not needed here, so I removed that, too. And the special handling of (shift % wordsize) == 0 was wrong because it did not handle all undefined shift values (negative values, values larger than wordsize). I removed it because compilers do the right thing in this example even if the C standard says it's undefined. See Linux or QEMU code for a reference (ror32, rol32). --Stefan Weil (talk) 05:59, 7 October 2013 (UTC)

Merger proposal

The article on this page refers to the same mathematical concept as Definition 1 in the article on cyclic permutation. It seems to me that usage of the term cyclic shift predominates in computer science (including theoretical computer science), whereas the term cyclic permutation is preferred by pure mathematicians (in particular algebraists). Therefore I suggest to merge the two articles.Hermel (talk) 13:26, 31 December 2009 (UTC)

I'm against a merge, but in favour of reducing confusion. For this reason I just changed the mathematical portion of this article to be at least consistent with the meanings of "tuple" and "permutation". I also changed the example to show why it matters. As for cyclic permutation, that article only disseminates confusion, so I would prefer that it were just removed or at best reduced to a disambiguation page (I've just added a citation tag to see if all the conflicting meanings it mentions are really used like that). Any useful stuff that it might contain might be integrated (carefully) either here or in cycle or Cycles and fixed points or whatever other related article I might have overlooked. Marc van Leeuwen (talk) 10:58, 21 January 2010 (UTC)

Diagram is not useful

Either text should be added to the article explaining how the diagram relates to circular shifts, or the diagram should be replaced with something that clearly illustrates circular shifts. It is unclear, for example, how the sequence "A051683 Triangle read by rows: a(n,k)=n!*k." is relevant, let alone the rest of the diagram. --24.47.169.50 (talk) 16:46, 26 April 2015 (UTC)