136:
127:
25:
1028:
1013:
557:
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.
168:, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of
299:
232:
476:
1190:
with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a
1445:
1417:
T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE,
521:, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.
89:
61:
68:
108:
1509:
42:
75:
46:
423:
and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all
257:
190:
1514:
1000:
If the bit sequence 0001 0111 were subjected to a circular shift of one bit position... (see images below)
57:
501:, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an
549:
has ROL and ROR). However, some compilers may provide access to the processor instructions by means of
984:
in the C language standard. However, it tends to work anyway, because most microprocessors implement
1372:
1191:
454:
135:
1337:
534:
126:
35:
1266:
537:, do not have operators or standard functions for circular shifting, even though virtually all
1478:
1274:
538:
506:
82:
1430:
A. N. Maslov, "Cyclic shift operation for languages", Problems of
Information Transmission
1361:
494:
1474:
8:
981:
533:
in order to permute bit sequences. Unfortunately, many programming languages, including
1290:
550:
319:
The result of repeatedly applying circular shifts to a given tuple are also called the
301:
234:
169:
144:
1210:
542:
447:) only has 2 distinct circular shifts. The number of distinct circular shifts of an
1470:
1460:
502:
498:
1254:
988:
as either a 32-bit shift (producing 0) or a 0-bit shift (producing the original
1322:
1298:
1465:
1406:
16:
Circular shifts: Mathematical concept and applications in software development
1503:
518:
154:
1395:
587:// for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
530:
1039:
If the bit sequence 1001 0110 were subjected to the following operations:
505:, a circular shift does not preserve a number's sign bit or distinguish a
1332:
1183:
878:
514:
177:
173:
157:
1375:
mentions that this code supports the "rotate" instruction in the CellSPU
1384:
1187:
572:* The mask, used with bitwise-and (&), prevents undefined behaviour
1327:
546:
326:
For example, repeatedly applying circular shifts to the four-tuple (
24:
992:), and either one produces the correct result in this application.
566:* Shift operations in C are only defined for shift values which are
510:
1446:"Language operations with regular expressions of polynomial size"
490:, indicating the maximal number of repeats over all subpatterns.
483:
877:
This safe and compiler-friendly implementation was developed by
1027:
575:* when the shift count is 0 or >= the width of unsigned int.
554:
1012:
1407:
Near constant time rotate that does not violate the standards
1341:
165:
569:* not negative and smaller than sizeof(value) * CHAR_BIT.
1344:
but for which circular shifts are considered equivalent.
1229:) denote the set of all circular shifts of strings in
457:
431:
distinct circular shifts. For instance, the 4-tuple (
260:
193:
1048:
0010 1101
49:. Unsourced material may be challenged and removed.
1396:Stackoverflow: Best practices for rotates in C/C++
470:
293:
226:
147:of 8-element circular shifts to the left and right
980:is 0 or 32, it asks for a 32-bit shift, which is
164:is the operation of rearranging the entries in a
1501:
524:
1385:Safe, Efficient, and Portable Rotate in C/C++
1443:
553:. In addition, some constructs in standard
1297:, there is a regular expression of length
1464:
1373:"Cleanups in ROTL/ROTR DAG combiner code"
976:This version is dangerous because if the
888:is limited to the range of 1 to 31 bits:
884:A simpler version is often seen when the
109:Learn how and when to remove this message
1444:Gruber, Hermann; Holzer, Markus (2009).
1362:GCC: "Optimize common rotate constructs"
1026:
1011:
881:, and further polished by Peter Cordes.
184:entries in the tuple such that either
1502:
294:{\displaystyle \sigma (i)\equiv (i-1)}
227:{\displaystyle \sigma (i)\equiv (i+1)}
1169:right circular shift by 8 positions:
1161:right circular shift by 7 positions:
1153:right circular shift by 6 positions:
1145:right circular shift by 5 positions:
1137:right circular shift by 4 positions:
1129:right circular shift by 3 positions:
1121:right circular shift by 2 positions:
172:, which in turn is a special kind of
1249:; this is a necessary condition for
1113:right circular shift by 1 position:
1101:left circular shift by 8 positions:
1093:left circular shift by 7 positions:
1085:left circular shift by 6 positions:
1077:left circular shift by 5 positions:
1069:left circular shift by 4 positions:
1061:left circular shift by 3 positions:
1053:left circular shift by 2 positions:
1023:to the right would yield: 1000 1011.
47:adding citations to reliable sources
18:
1045:left circular shift by 1 position:
13:
1285:) is again context-free. Also, if
1008:to the left would yield: 0010 1110
529:Circular shifts are used often in
176:. Formally, a circular shift is a
14:
1526:
134:
125:
23:
1178:
34:needs additional citations for
1437:
1424:
1411:
1400:
1389:
1378:
1366:
1355:
471:{\displaystyle {\frac {n}{k}}}
288:
276:
270:
264:
221:
209:
203:
197:
1:
1348:
1453:Theoretical Computer Science
525:Implementing circular shifts
419:) (the original four-tuple),
7:
1316:
10:
1531:
995:
545:instructions for it (e.g.
1466:10.1016/j.tcs.2009.04.009
890:
560:
1237:is a cyclic code, then
1510:Elementary mathematics
1267:formal language theory
1265:) has been studied in
1213:of circular shifts of
1032:
1017:
472:
295:
228:
1275:context-free language
1031:Right circular shift.
1030:
1015:
507:floating-point number
473:
342:) successively gives
296:
229:
1016:Left circular shift.
495:computer programming
455:
258:
191:
43:improve this article
1515:Computer arithmetic
1340:— an object like a
1269:. For instance, if
982:undefined behaviour
551:intrinsic functions
1291:regular expression
1289:is described by a
1033:
1018:
468:
307:, for all entries
291:
240:, for all entries
224:
170:cyclic permutation
1459:(35): 3281–3289.
1197:over an alphabet
1176:
1175:
1108:
1107:
1037:
1036:
986:value >> 32
543:bitwise operation
466:
119:
118:
111:
93:
1522:
1494:
1492:
1490:
1489:
1483:
1477:. Archived from
1468:
1450:
1441:
1435:
1428:
1422:
1415:
1409:
1404:
1398:
1393:
1387:
1382:
1376:
1370:
1364:
1359:
1257:. The operation
1221:of strings, let
1217:, and for a set
1110:
1109:
1042:
1041:
1003:
1002:
991:
987:
979:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
887:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
593:<limits.h>
591:
588:
585:
584:<stdint.h>
582:
579:
576:
573:
570:
567:
564:
503:arithmetic shift
499:bitwise rotation
489:
481:
477:
475:
474:
469:
467:
459:
300:
298:
297:
292:
233:
231:
230:
225:
138:
129:
114:
107:
103:
100:
94:
92:
58:"Circular shift"
51:
27:
19:
1530:
1529:
1525:
1524:
1523:
1521:
1520:
1519:
1500:
1499:
1498:
1497:
1487:
1485:
1481:
1448:
1442:
1438:
1434::333–338, 1973.
1429:
1425:
1421::119–122, 1972.
1416:
1412:
1405:
1401:
1394:
1390:
1383:
1379:
1371:
1367:
1360:
1356:
1351:
1319:
1255:cyclic language
1181:
998:
989:
985:
977:
974:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
885:
875:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
596:// for CHAR_BIT
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
527:
487:
479:
458:
456:
453:
452:
321:circular shifts
259:
256:
255:
192:
189:
188:
151:
150:
149:
148:
141:
140:
139:
131:
130:
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
1528:
1518:
1517:
1512:
1496:
1495:
1436:
1423:
1410:
1399:
1388:
1377:
1365:
1353:
1352:
1350:
1347:
1346:
1345:
1335:
1330:
1325:
1323:Barrel shifter
1318:
1315:
1186:are a kind of
1180:
1177:
1174:
1173:
1170:
1166:
1165:
1162:
1158:
1157:
1154:
1150:
1149:
1146:
1142:
1141:
1138:
1134:
1133:
1130:
1126:
1125:
1122:
1118:
1117:
1114:
1106:
1105:
1102:
1098:
1097:
1094:
1090:
1089:
1086:
1082:
1081:
1078:
1074:
1073:
1070:
1066:
1065:
1062:
1058:
1057:
1054:
1050:
1049:
1046:
1035:
1034:
1025:
1024:
1019:
1010:
1009:
997:
994:
891:
561:
526:
523:
465:
462:
421:
420:
401:
382:
363:
323:of the tuple.
317:
316:
290:
287:
284:
281:
278:
275:
272:
269:
266:
263:
249:
248:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
162:circular shift
143:
142:
133:
132:
124:
123:
122:
121:
120:
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1527:
1516:
1513:
1511:
1508:
1507:
1505:
1484:on 2017-08-29
1480:
1476:
1472:
1467:
1462:
1458:
1454:
1447:
1440:
1433:
1427:
1420:
1414:
1408:
1403:
1397:
1392:
1386:
1381:
1374:
1369:
1363:
1358:
1354:
1343:
1339:
1336:
1334:
1331:
1329:
1326:
1324:
1321:
1320:
1314:
1312:
1308:
1305:) describing
1304:
1300:
1296:
1292:
1288:
1284:
1280:
1276:
1272:
1268:
1264:
1260:
1256:
1252:
1248:
1244:
1240:
1236:
1232:
1228:
1224:
1220:
1216:
1212:
1209:) denote the
1208:
1204:
1200:
1196:
1193:
1189:
1185:
1171:
1168:
1167:
1163:
1160:
1159:
1155:
1152:
1151:
1147:
1144:
1143:
1139:
1136:
1135:
1131:
1128:
1127:
1123:
1120:
1119:
1115:
1112:
1111:
1103:
1100:
1099:
1095:
1092:
1091:
1087:
1084:
1083:
1079:
1076:
1075:
1071:
1068:
1067:
1063:
1060:
1059:
1055:
1052:
1051:
1047:
1044:
1043:
1040:
1029:
1022:
1021:
1020:
1014:
1007:
1006:
1005:
1004:
1001:
993:
983:
889:
882:
880:
559:
556:
552:
548:
544:
540:
536:
532:
522:
520:
519:logical shift
516:
512:
508:
504:
500:
496:
491:
485:
463:
460:
450:
446:
442:
438:
434:
430:
427:-tuples have
426:
418:
414:
410:
406:
402:
399:
395:
391:
387:
383:
380:
376:
372:
368:
364:
361:
357:
353:
349:
345:
344:
343:
341:
337:
333:
329:
324:
322:
314:
310:
306:
303:
285:
282:
279:
273:
267:
261:
254:
253:
252:
247:
243:
239:
236:
218:
215:
212:
206:
200:
194:
187:
186:
185:
183:
179:
175:
171:
167:
163:
159:
156:
155:combinatorial
146:
137:
128:
113:
110:
102:
99:December 2009
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
1486:. Retrieved
1479:the original
1456:
1452:
1439:
1431:
1426:
1418:
1413:
1402:
1391:
1380:
1368:
1357:
1310:
1306:
1302:
1294:
1286:
1282:
1278:
1270:
1262:
1258:
1250:
1246:
1242:
1238:
1234:
1230:
1226:
1222:
1218:
1214:
1206:
1202:
1198:
1194:
1184:Cyclic codes
1182:
1179:Applications
1038:
999:
975:
883:
876:
531:cryptography
528:
492:
448:
444:
440:
436:
432:
428:
424:
422:
416:
412:
408:
404:
397:
393:
389:
385:
378:
374:
370:
366:
359:
355:
351:
347:
339:
335:
331:
327:
325:
320:
318:
312:
308:
304:
250:
245:
241:
237:
181:
161:
152:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
1333:Lyndon word
879:John Regehr
517:. Unlike a
515:significand
178:permutation
174:permutation
158:mathematics
1504:Categories
1488:2012-09-06
1475:1176.68105
1349:References
1293:of length
1188:block code
1172:1001 0110
1164:0010 1101
1156:0101 1010
1148:1011 0100
1140:0110 1001
1132:1101 0010
1124:1010 0101
1116:0100 1011
1104:1001 0110
1096:0100 1011
1088:1010 0101
1080:1101 0010
1072:0110 1001
1064:1011 0100
1056:0101 1010
539:processors
451:-tuple is
311:= 1, ...,
244:= 1, ...,
69:newspapers
1328:Circulant
547:Intel x86
513:from its
283:−
274:≡
262:σ
207:≡
195:σ
180:σ of the
1338:Necklace
1317:See also
1253:being a
953:>>
935:<<
911:unsigned
902:uint32_t
893:uint32_t
851:<<
833:>>
785:CHAR_BIT
773:unsigned
755:unsigned
746:uint32_t
737:uint32_t
713:>>
695:<<
647:CHAR_BIT
635:unsigned
617:unsigned
608:uint32_t
599:uint32_t
590:#include
581:#include
511:exponent
478:, where
145:Matrices
1277:, then
996:Example
484:divisor
83:scholar
1473:
1201:, let
1192:string
926:return
896:rotl32
824:return
815:&=
791:sizeof
740:rotr32
686:return
677:&=
653:sizeof
602:rotl32
555:ANSI C
302:modulo
235:modulo
85:
78:
71:
64:
56:
1482:(PDF)
1449:(PDF)
1342:tuple
1307:shift
1279:shift
1273:is a
1259:shift
1239:shift
1233:. If
1223:shift
1203:shift
990:value
978:count
965:count
950:value
938:count
932:value
917:count
905:value
886:count
863:&
860:count
848:value
836:count
830:value
812:count
797:value
770:const
761:count
749:value
725:&
722:count
710:value
698:count
692:value
674:count
659:value
632:const
623:count
611:value
541:have
482:is a
166:tuple
90:JSTOR
76:books
1245:) ⊆
866:mask
818:mask
779:mask
728:mask
680:mask
641:mask
497:, a
160:, a
62:news
1471:Zbl
1461:doi
1457:410
1419:55D
1313:).
1211:set
968:));
914:int
869:));
776:int
758:int
731:));
638:int
620:int
509:'s
493:In
486:of
251:or
153:In
45:by
1506::
1469:.
1455:.
1451:.
959:32
578:*/
563:/*
443:,
439:,
435:,
415:,
411:,
407:,
400:),
396:,
392:,
388:,
381:),
377:,
373:,
369:,
362:),
358:,
354:,
350:,
338:,
334:,
330:,
1493:.
1491:.
1463::
1432:9
1311:L
1309:(
1303:n
1301:(
1299:O
1295:n
1287:L
1283:L
1281:(
1271:L
1263:L
1261:(
1251:L
1247:L
1243:L
1241:(
1235:L
1231:L
1227:L
1225:(
1219:L
1215:s
1207:s
1205:(
1199:Σ
1195:s
971:}
962:-
956:(
947:(
944:|
941:)
929:(
923:{
920:)
908:,
899:(
872:}
857:-
854:(
845:(
842:|
839:)
827:(
821:;
809:;
806:1
803:-
800:)
794:(
788:*
782:=
767:{
764:)
752:,
743:(
734:}
719:-
716:(
707:(
704:|
701:)
689:(
683:;
671:;
668:1
665:-
662:)
656:(
650:*
644:=
629:{
626:)
614:,
605:(
535:C
488:n
480:k
464:k
461:n
449:n
445:b
441:a
437:b
433:a
429:n
425:n
417:d
413:c
409:b
405:a
403:(
398:a
394:d
390:c
386:b
384:(
379:b
375:a
371:d
367:c
365:(
360:c
356:b
352:a
348:d
346:(
340:d
336:c
332:b
328:a
315:.
313:n
309:i
305:n
289:)
286:1
280:i
277:(
271:)
268:i
265:(
246:n
242:i
238:n
222:)
219:1
216:+
213:i
210:(
204:)
201:i
198:(
182:n
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
