Talk:Circular shift

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics
WikiProject Computer science (Rated Stub-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 

Terminology[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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)