Content deleted Content added
RProgrammer (talk | contribs) Added Necklaces to See Also :) |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Elementary mathematics | #UCB_Category 19/56 |
||
| (13 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Circular shifts: Mathematical concept and applications in software development}}
{{Refimprove|date=December 2009}}
{{multiple image
Line 21 ⟶ 22:
* (''b'', ''c'', ''d'', ''a''),
* (''a'', ''b'', ''c'', ''d'') (the original four-tuple),
and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all ''n''-tuples have ''n'' distinct circular shifts. For instance, the 4-tuple (''a'', ''b'', ''a'', ''b'') only has 2 distinct circular shifts.
In [[computer programming]], a [[bitwise rotation]], also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an [[arithmetic shift]], a circular shift does not preserve a number's sign bit or distinguish a [[floating-point number]]'s [[exponent]] from its [[significand]]. Unlike a [[logical shift]], the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.
Line 27 ⟶ 28:
== Implementing circular shifts ==
<!-- Courtesy note per [[MOS:LINK2SECT]]: [[Bitwise operation]] links here -->
Circular shifts are used often in [[cryptography]] in order to permute bit sequences. Unfortunately, many programming languages, including [[C (programming language)|C]], do not have operators or standard functions for circular shifting, even though virtually all [[Processor (computing)|processors]] have [[bitwise operation]] instructions for it (e.g. [[Intel x86]] has ROL and ROR).
However, some compilers may provide access to the processor instructions by means of [[intrinsic function]]s. In addition, some constructs in standard [[ANSI C]] code may be optimized by a compiler to the "rotate" assembly language instruction on CPUs that have such an instruction. Most C compilers recognize the following idiom, and compile it to a single 32-bit rotate instruction.<ref>
[https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html GCC: "Optimize common rotate constructs"]
</ref><ref>
Line 63 ⟶ 64:
<syntaxhighlight lang="C">
uint32_t rotl32 (uint32_t value, unsigned int count) {
return (value << count) | (value >> (32 - count));
}
</syntaxhighlight>
Line 139 ⟶ 140:
[[Cyclic code]]s are a kind of [[block code]] with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a [[string (computer science)|string]] ''s'' over an alphabet ''Σ'', let ''shift''(''s'') denote the [[set (mathematics)|set]] of circular shifts of ''s'',
and for a set ''L'' of strings, let ''shift''(''L'') denote the set of all circular shifts of strings in ''L''. If ''L'' is a cyclic code, then ''shift''(''L'') ⊆ ''L''; this is a necessary condition for ''L'' being a [[cyclic language]]. The operation ''shift''(''L'') has been studied in [[formal language theory]]. For instance, if ''L'' is a [[context-free language]], then ''shift''(''L'') is again context-free.<ref>T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, '''55D''':119–122, 1972.
</ref><ref>A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission '''9''':333–338, 1973.</ref> Also, if ''L'' is described by a [[regular expression]] of length ''n'', there is a regular expression of length [[Big O notation|O]](''n''<sup>3</sup>) describing ''shift''(''L'').<ref>{{cite journal | zbl=1176.68105 | last1=Gruber | first1=Hermann | last2=Holzer | first2=Markus | title=Language operations with regular expressions of polynomial size
==See also==
*[[Barrel shifter]]
*[[Circulant]]
*[[Lyndon word]]
| |||