challenge ローテートシフト

ローテートシフトを実装してください。

例)
0010 0011 1110 1101
↓右に1ビットローテート
1001 0001 1111 0110

ローテートシフトがある言語がどれ位あるか知りたくなって投稿しました。

Posted feedbacks - Nested

Flatten Hidden
rotate_r(parseInt("0010001111101101",2), 1).toString(2)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//文字列を指定数倍する
if(!String.prototype.x){
    String.prototype.x = function(n){
        var result="";
        for(var i=0;i<n;i++){
            result += this;
        }
        return result;
    }
}
//指定された桁数まで文字を補う
function paddingLeft(str, d, c){
    var len  = str.toString().length;
    var x = d > len ? d - len : 0;
    
    return c.x(x) + str;
}

function rotate_r(n, count, size){
    size = size | 16;//デフォルトは、16ビットで処理
    var wk_bin = paddingLeft(n.toString(2), size, '0');
    var over = wk_bin.substr(-count);
    wk_bin = over + wk_bin.substr(0, wk_bin.length - count);
    return parseInt(wk_bin, 2);
}
size = size | 16; は、 size = size || 16; の間違い
substr(-count) は、 slice(-count) の間違い

そのまま

1
2
3
(import (rnrs))

(bitwise-rotate-bit-field #b0010001111101101 0 16 -1)

Squeak Smalltalk で。

1
2
3
4
5
6
7
| bitRotate16 |
bitRotate16 := [:val :shift |
    shift := shift \\ 16.
    (val << (16 - shift) bitOr: val >> shift) bitAnd: 16rFFFF].

(bitRotate16 valueWithArguments: #(2r0010001111101101 1)) radix: 2
"=> '1001000111110110' "

Javaにはローテートシフトがないらしいので、こんな感じで実装。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * 左ローテートシフト
 * @param value 値
 * @param n シフトさせるビット数
 * @return 左ローテートシフト後の値
 */
public static int leftRotateShift(int value, int n) {
    return (value << n) | (value >>> (32 - n));
}

/**
 * 右ローテートシフト
 * @param value 値
 * @param n シフトさせるビット数
 * @return 右ローテートシフト後の値
 */
public static int rightRotateShift(int value, int n) {
    return (value >>> n) | (value << (32 - n));
}

ローテートシフトありますよ!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class RotateShift {
   public static void main(String[] args) {
      int input = Integer.parseInt("0010001111101101", 2);

      int i = Integer.rotateRight(input, 1);
      System.out.printf("%s%n",Integer.toString(i, 2));
      System.out.printf("%s%n",Integer.toString((short)i, 2));

      long l = Long.rotateRight(input, 1);
      System.out.printf("%s%n",Long.toString(l, 2));
      System.out.printf("%s%n",Long.toString((short)l, 2));
   }
}


/* -- 実行結果 --
-1111111111111111110111000001010
1000111110110
-111111111111111111111111111111111111111111111111110111000001010
1000111110110
*/
ありゃ、ホントですね。
1.5から増えたんですね。勉強になりました。
整数(Cのlong)が64bitである前提です。

$ rotR 300 2
75
$ rotR -2 4
-1152921504606846977
$ rotL 300 4
4800
$ rotL -2 4
-17
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function rotR() {
    local i=$1
    local w=$2
    echo $((i >> w & ~(-1 << 64 - w) | i << 64 - w))
}

function rotL() {
    local i=$1
    local w=$2
    echo $((i >> 64 - w & ~(-1 << w) | i << w))
}

long の bit 数は -1 の hex 表現から簡単に得られますよ。

1
2
local minus_one_in_hex=$(printf %x -1)
local -i sizeof_long="${#minus_one_in_hex} * 4"

tsekineさん、ナイスです。

ということでマージしてみます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
printf -v minus_one_in_hex %x -1
typeset -i sizeof_long="${#minus_one_in_hex} * 4"
unset minus_one_in_hex

function rotR() {
    local i=$1
    local w=$2
    echo $((i >> w & ~(-1 << sizeof_long - w) | i << 64 - w))
}

function rotL() {
    local i=$1
    local w=$2
    echo $((i >> sizeof_long - w & ~(-1 << w) | i << w))
}

もう少しコードは短縮できるがコンパイラの最適化を阻害しそうなので止めた

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
void rotate (char *str,int num);
/*
 *第一引数 rotateする文字列
 *第二引数 rotateする回数(int型、正の場合、左、負の場合、右にrotateする)
 *
 * 引数が二個未満または第二引数がint型と解釈できない文字列ならば
 * Segmentation fault が発生するので注意
 */
int main( int argc, char *argv[] ){
  rotate(argv[1],atoi(argv[2]));
}
/*
 * 引数str  rotateする文字列
 * 引数num  正の場合、左にnum個シフトする
 *        負の場合、右にnum個シフトする
 */
void rotate(char *str,int num){
  int str_length = strlen(str);
  int rotate_num = num>=0?abs(num)% str_length:-abs(num)% str_length;
  char rotated_str[str_length];
    int i;
    if(num>=0){
      for(i=0;i<str_length;i++){
    rotated_str[i]=str[i+rotate_num<str_length?i+rotate_num:i+rotate_num-str_length];
      }
    }
    else{
      for(i=0;i<str_length;i++){
    rotated_str[i]=str[i+rotate_num>=0?i+rotate_num:i+rotate_num+str_length];
      }
    }
  rotated_str[str_length]='\0';
  printf("%s\n",rotated_str);
}

VBAでIntegerの値をローテートシフトするコードを書いてみました。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
Option Explicit

Sub main()
    Dim Value As Integer
    
    Value = 9197
    
    Debug.Print "  " & Value & " : " & Bin(Value)
        
    Debug.Print "↓右に1ビットローテート"
    Value = RotateRight(Value)
    
    Debug.Print Value & " : " & Bin(Value)
    
    Debug.Print "↓左に1ビットローテート"
    Value = RotateLeft(Value)
    
    Debug.Print "  " & Value & " : " & Bin(Value)
End Sub

'// Integerの値を右ローテートシフトする。
Function RotateRight(Value As Integer) As Integer
    Dim Bak As Integer
    Dim BinStr As String
    
    '// 指定されたIntegerの値を二進数文字列に変換する。
    BinStr = Bin(Value)
    '// 二進数文字列を右ローテートシフトする。
    BinStr = Right(BinStr, 1) & Left(BinStr, 15)
    '// ローテートされた二進数文字列をIntegerの値に変換する。
    Bak = Dec(BinStr)
    
    RotateRight = Bak
End Function

'// Integerの値を左ローテートシフトする。
Function RotateLeft(Value As Integer) As Integer
    Dim Bak As Integer
    Dim BinStr As String
    
    '// 指定されたIntegerの値を二進数文字列に変換する。
    BinStr = Bin(Value)
    '// 二進数文字列を左ローテートシフトする。
    BinStr = Right(BinStr, 15) & Left(BinStr, 1)
    '// ローテートされた二進数文字列をIntegerの値に変換する。
    Bak = Dec(BinStr)
    
    RotateLeft = Bak
End Function

'// 指定されたIntegerの値を二進数文字列に変換する。
Function Bin(ByVal Value As Integer) As String
    Dim Bak As String
    Dim AbsValue As Long
    
    '// 指定された値の絶対値を取得する。
    AbsValue = Abs(CLng(Value))
    '// 絶対値を二進数文字列に変換する。
    Bak = PosValueToBin(AbsValue)
    '// 二進数文字列の長さを16ビットにする。
    Bak = SetSize(Bak, 16)
    
    '// 指定された値が負の数であることを確認する。
    If Value < 0 Then
        '// 二進数文字列の二の補数を求める。
        Bak = Complement(Bak)
    End If
    
    Bin = Bak
End Function

'// 指定された二進数文字列をIntegerの値に変換する。
Function Dec(ByVal BinStr As String) As Integer
    Dim Bak As Long
    Dim Flag As Long

    '// 二進数文字列が負の数であることを確認する。
    '// 二進数文字列の先頭ビットが1の場合、負の数であることが確認できる。
    If Left(BinStr, 1) = "1" Then
        '// 二進数文字列の二の補数を求める。
        BinStr = Complement(BinStr)
        '// 符号をマイナスにする。
        Flag = -1
    Else
        '// 符号をプラスにする。
        Flag = 1
    End If
    
    '// 二進数文字列をLong値に変換する。
    Bak = PosBinToLong(BinStr)
    '// Long値に符号を適用する。
    Bak = Flag * Bak
        
    Dec = CInt(Bak)
End Function

'// 正の数を二進数文字列に変換する。
Function PosValueToBin(PosValue As Long) As String
    Dim Bak As String

    Bak = ""
    Do While PosValue > 0
        Bak = PosValue Mod 2 & Bak
        PosValue = PosValue \ 2
    Loop
    
    PosValueToBin = Bak
End Function

'// 正の二進数文字列をLongに変換する。
Function PosBinToLong(BinStr As String) As Long
    Dim Bak As Long
    Dim i As Integer
    
    Bak = 0
    For i = 1 To Len(BinStr)
        Bak = Bak * 2
        Bak = Bak + Mid(BinStr, i, 1)
    Next
    
    PosBinToLong = Bak
End Function

'// 二進数文字列を指定されたサイズにする。
Function SetSize(BinStr As String, NewSize As Integer) As String
    Dim Bak As String
    Dim i As Long
    Dim Lack As Long
    Dim OldSize As Long
    
    '// 二進数文字列のサイズを指定されたサイズと比較する。
    OldSize = Len(BinStr)
    If NewSize < OldSize Then
        '// 二進数文字列のサイズが指定されたサイズより大きい:
        
        Bak = Right(BinStr, NewSize)
    
    ElseIf NewSize > OldSize Then
        '// 二進数文字列のサイズが指定されたサイズより小さい:
        
        '足りないサイズを求める。
        Lack = NewSize - OldSize
        '足りないサイズ分を0で埋める。
        Bak = BinStr
        For i = 1 To Lack
            Bak = "0" & Bak
        Next
        
    Else
        '// 二進数文字列のサイズと指定されたサイズが等しい:
        
        Bak = BinStr
        
    End If
        
    SetSize = Bak
End Function

'// 二進数文字列の二の補数を求める。
Function Complement(BinStr As String) As String
    Dim Bak As String
    
    '// 二進数文字列の符号を反転させる。
    Bak = Reverse(BinStr)
    '// 二進数文字列に1を足す。
    Bak = PlusOne(Bak)
    
    Complement = Bak
End Function

'// 二進数文字列の各ビットを反転させる。
Function Reverse(BinStr As String) As String
    Dim Bak As String
    Dim i As Integer

    Bak = ""
    For i = 1 To Len(BinStr)
        If Mid(BinStr, i, 1) = "0" Then
            Bak = Bak & "1"
        Else
            Bak = Bak & "0"
        End If
    Next
    
    Reverse = Bak
End Function

'// 二進数文字列の1を足す。
Function PlusOne(BinStr As String) As String
    Dim Bak As String
    Dim i As Integer

    Bak = ""
    
    i = Len(BinStr)
    
    Do While i >= 1
        If Mid(BinStr, i, 1) = "0" Then
            Bak = "1" & Bak
            i = i - 1
            Exit Do
        Else
            Bak = "0" & Bak
            i = i - 1
        End If
    Loop
    
    Do While i >= 1
        Bak = Mid(BinStr, i, 1) & Bak
        i = i - 1
    Loop
    
    PlusOne = Bak
End Function

' -- 実行結果 --
'  9197 : 0010001111101101
'↓右に1ビットローテート
'-28170 : 1001000111110110
'↓左に1ビットローテート
'  9197 : 0010001111101101

Tera Termのマクロです。 海外からの要望で実装されました。

1
2
3
4
5
6
7
8
9
a = $12345678

rotateright b a 4
sprintf "%08x -> %08x" a b
messagebox inputstr "4 bit right rotate"

rotateleft b a 4
sprintf "%08x -> %08x" a b
messagebox inputstr "4 bit left rotate"

ANSI CL標準には含まれていませんが、処理系の拡張として持っているものもあるようです(SBCL等) ここではcl-utilitiesを使いました。

1
2
(cl-utilities:ROTATE-BYTE -1 (byte 16 0) #b0010001111101101)
;=> 37366(#b1001000111110110)

引数に2進数と桁数を与えると、与えられた2進数を右に1ビットだけローテートシフトした2進数を文字列で返すメソッドrotate_rの実装です。実行結果は次のとおり:

irb(main):005:0> rotate_r(0b0010001111101101, 16)
=> "1001000111110110"
irb(main):006:0>
1
2
3
4
def rotate_r(bin_num, digit)
  bin_num.to_s(2).rjust(digit, '0')[-digit, digit].each_char.
    cycle.take(digit * 2 - 1)[-digit, digit].join
end

Haskell にもローテートシフトありますよ。(仕様で入ってるかどうかはわかりませんが)ghc の base ライブラリの中の Data.Bits モジュールに入ってます。

ありますよで終わってしまうのはさみしいので QuickCheck してみました。

ローテートシフトなんだから、シフトした後逆方向に同じ幅だけシフトしたら元に戻るよね、というのをランダムな引数を与えて確かめています。シフトする幅に 0 が来たら、それはテストするまでもないので飛ばすことにします。実行ファイルの引数として verbose を渡すと、テストに渡された引数を出力させながらテストします。

~/work/2009/03/08 10:18 ghc --make rotateshift.hs
[1 of 1] Compiling Main             ( rotateshift.hs, rotateshift.o )
Linking rotateshift ...
~/work/2009/03/08 10:29 ./rotateshift
OK, passed 100 tests (18% trivial).
~/work/2009/03/08 10:29 ./rotateshift verbose
0:
2
3
1:
1
1
OK, passed 100 tests (11% trivial).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import Data.Bits
import Test.QuickCheck
import System.Environment

prop_rotate :: Int -> Int -> Property
prop_rotate bits n = trivial (n == 0) $ bits == rotate (rotate bits n) (-n)

main = do
  is_verbose <- verbose
  (if is_verbose then verboseCheck else quickCheck) prop_rotate

verbose = do
  args <- getArgs
  return $ if null args then False else head args == "verbose"

verbose のほうの出力は省略してます。

「ローテートシフトがある」とは言えませんが。

1
2
3
4
5
6
7
def rotate(n, width=16):
    s = bin(n)
    assert s[:2] == "0b"
    s = s[2:].zfill(width)
    return int(s[-1] + s[:-1], 2)

print rotate(9197)

文字列で右にローテート。 負の値を与えると左にローテート。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void rotate(char *str, int num);

int main(int argc, char *argv[])
{
  assert(argc > 2);
  rotate(argv[1], atoi(argv[2]));
  puts(argv[1]);
  return 0;
}

void rotate(char *str, int num)
{
  size_t len = strlen(str);
  size_t n = num % len;
  char *tmp;

  tmp = malloc(n);
  memcpy(tmp, str+len-n, n);
  memmove(str+n, str, len-n);
  memcpy(str, tmp, n);
  free(tmp);
}
とりあえず、右ローテートシフト 1ビット固定で^^;
Cの場合、インラインアセンブラを使ってしまうのが一番手っ取り早い?

CPU依存してしまうから嫌われるかもしれませんが。。。
# 初めて使ったけど gccってasm{} 使えないことをしった今日この頃

// gcc -Wall doukaku239.c
// CPU は x86系限定です。
%  ./a.out 7
before: 00000000000000000000000000000111
after : 10000000000000000000000000000011
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int print_bits(uint32_t in)
{
        char bits[33] = "00000000000000000000000000000000";
        char *p = bits;
        int carry=0;

        while( in > 0 )
        {
                __asm__("    shl $1,%2;\n"
                        "    pushf;\n"
                        "    pop %3;\n"
                        "    andl $1,%3;\n"
                        :"=c"(in), "=a"(carry)
                        : "0"(in), "1"(carry)
                );
                *p = '0' + carry; p ++;
        }
        printf("%.33s\n", bits);
        return 0;
}

int main(int argc, char *argv[])
{
        uint32_t param = 0;
        param = atoi(argv[1]);
        printf("before: "); print_bits( param );
        __asm__("    ror $1,%1" : "=r"(param) : "0"(param) );
        printf("after : "); print_bits( param );
        return 0;
}
Cで。
64bit整数に2個つめてからシフトしています。
マイナスシフト(左シフト)、32を超えるシフトにも対応。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>

#ifdef _MSC_VER
    typedef _int32 int32_t;
    typedef _int64 int64_t;
#elif __GNUC__
    #include <stdint.h>
#endif

/* rotate : numをshift回だけ右にローテートシフトする */
int32_t rotate(int32_t num, int shift)
{
    int64_t numnum;
    /* シフト数の正規化(32以下の正数にする) */
    while (shift < 0) shift+= 32;
    shift %= 32;
    /* シフト */
    numnum = num;
    numnum = (numnum<<32) | num;
    return (numnum>>shift) & (int32_t)-1;
}

int main(int argc, char *argv[])
{
    char buf[32+1];
    int32_t num = 0;
    int32_t num2 = 0;
    int shift = 1;

    if (argc < 2) {
        printf("Usage: %s <bits> <shift>\n", argv[0]);
        return EXIT_FAILURE;
    } else if (argc == 2) {
        num = strtol(argv[1], NULL, 2);
    } else if (argc > 2) {
        num = strtol(argv[1], NULL, 2);
        shift = strtol(argv[2], NULL, 10);
    }
    num2 = rotate(num, shift);
    printf("%032s\n", itoa(num2, buf, 2));
    return EXIT_SUCCESS;
}

右シフトで消える部分を左に持ってきて、後でそれをorでつなぎます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System;
class P
{
    static void Main()
    {
        ushort value = 0x23ed;
        Console.WriteLine(ToBinStr(value));
        Console.WriteLine(ToBinStr(Rotate(value, 1)));
    }
    static ushort Rotate(ushort value, short n)
    {
        return (ushort)((value >> n)
               | (value << (16 - n)));
    }
    static string ToBinStr(ushort value)
    {
        ushort end = 0x1110;
        string str = "";
        for (ushort i = 0x8000; i != 0; i >>= 1)
        {
            str += (value & i) != 0 ?
                        '1' : '0';
            if ((i & end) != 0)
                str += ' ';
        }
        return str;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bitset>

template<std::size_t N>
std::bitset<N> rotateRight(const std::bitset<N>& bits, int n)
{
    n %= N;
    return (bits >> n) | (bits << (N - n));
}

#include <iostream>

int main(int, char* [])
{
    std::bitset<16> bits(std::string("0010001111101101"));

    std::cout << bits << std::endl;
    std::cout << rotateRight(bits, 1) << std::endl;

    return 0;
}
1
2
3
4
5
6
program doukaku239

  print *, ishftc(9197, 1)

  stop
end program doukaku239
1
2
3
4
5
6
7
8
9
<?php

function rotateShift($value, $n)
{
    return substr(str_repeat(sprintf("%016b", bindec($value)), 3), 16-$n, 16);
}

$value = "0010001111101101";
var_dump(rotateShift($value, 1));
1
2
3
4
5
6
7
#module
// ローテートシフト関数
#define global ctype \
 RotateShift(%1=0,%2=32) _RotateShift(%1,%2)
#defcfunc _RotateShift int value, int bits
    return ((value & 1) << (bits - 1)) | (value >> 1)
#global
小細工してみたローテートシフト
テンプレートとかオペレータ使ってみるのが自分の好み
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <climits>

template<typename T_Type>
class RotateShift
{
// friend
    template<typename T_FuncArgType>
    friend RotateShift<T_FuncArgType> Rotate(const T_FuncArgType& rValue);

// 定数
private:
    static const unsigned int MEMBER_BIT_SIZE = sizeof(T_Type) * CHAR_BIT;

// コンストラクタ
private:
    RotateShift(const T_Type& rValue)
        : mrValue(rValue)
    {
    }

// メソッド
public:
    // 右シフト
    T_Type operator >>(int ShiftNum)
    {
        return (mrValue << (MEMBER_BIT_SIZE - ShiftNum)) | (mrValue >> ShiftNum);
    }
    // 左シフト
    T_Type operator <<(int ShiftNum)
    {
        return (mrValue << ShiftNum) | (mrValue >> (MEMBER_BIT_SIZE - ShiftNum));
    }

// メンバ変数
private:
    const T_Type& mrValue;
};


template<typename T_Type>
RotateShift<T_Type> Rotate(const T_Type& rValue)
{
    return rValue;
}

#include <bitset>
#include <iostream>

using namespace std;

int main(void)
{
    // 初期値表示
    bitset<16> Bit(string("0010001111101101"));
    cout << Bit << endl;

    // 右に1ビットシフト
    Bit = Rotate(Bit) >> 1;

    // 結果表示
    cout << Bit << endl;

    return 0;
}

perlで。

CPANには Bit::ShiftReg なるモジュールがあって、そこでもローテートシフトは実装されています

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
use strict;
use warnings;

our %mask;
sub _mask
{
  my $bits = shift;
  if ( exists $mask{$bits} ) {
    $mask{$bits};
  }
  else {
    my $mask = 0;
    for (my $i = 0; $i < $bits; ++$i) {
      $mask |= (1 << $i);
    }
    $mask{$bits}=$mask;
  }
}

# 右ローテート
sub rrotate
{
  my ($vec, $bits) = @_;

  my $lsb = $vec & 1;
  my $mask = _mask($bits) ^ (1<<($bits-1));

  (($vec >> 1) & $mask) | ($lsb?(1<<($bits-1)):0);
}

# 左ローテート
sub lrotate
{
  my ($vec, $bits) = @_;

  my $msb = $vec & (1<<($bits-1));
  my $mask = _mask($bits);

  (($vec << 1) & $mask) | ($msb?1:0);
}

print rrotate(0xdb, 8) == 0xed, "\n";
print lrotate(0xdb, 8) == 0xb7, "\n";
print rrotate(0xcafe, 16) == 0x657f, "\n";
print lrotate(0xcafe, 16) == 0x95fd, "\n";
print rrotate(0xcafe_babe, 16) == 0x5d5f, "\n"; # ignore 0xcafe
print lrotate(0xcafe_babe, 16) == 0x757d, "\n"; # ditto
print rrotate(0xcafe_babe, 32) == 0x657f_5d5f, "\n";
print lrotate(0xcafe_babe, 32) == 0x95fd_757d, "\n";
Visual C++には、ローテートが関数として用意されています。8/16/32/64ビットの左ローテートが_rotl8/_rotl16/_rotl/_rotl64、右ローテートは_rotr〜という名前です。なぜか、8/16ビットは<intrin.h>、32/64ビットは<stdlib.h>となっています。
1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned x = 0x84442211;
    printf("%08x\n%08x\n", x, _rotl(x, 1));
    return 0;
}

 Javaと同様IntegerのroteteRight/Leftメソッドを使って書いてみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
object RotateShift {
    def main(args:Array[String]):Unit =
        if (args.size != 3)
            println("usage: RotateShift VALUE (R|L) SHIFT")
        else {
            try {
                val    v:Int = Integer.parseInt(args(0), 2)
                val    s:Int = args(2).toInt
                println(
                    (args(1) match {
                        case "R" => Integer.rotateRight(v, s)
                        case "L" => Integer.rotateLeft(v, s)
                    }).toBinaryString
                )
            } catch {
                case _:IllegalArgumentException | _:scala.MatchError =>
                    println("引数の指定が不正です。")
                case e => e.printStackTrace
            }
        }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#! /usr/bin/ruby

class String
    def rot_shift
        result = split(//)
        result.unshift(result.pop).join
    end
end

p '0010001111101101'.rot_shift

SQL Server 2008 で確認しました。

1
2
3
4
5
6
7
8
9
WITH
  Input(bits) AS (
    SELECT '0010001111101101'
  )
SELECT
    RIGHT(bits, 1)
      + SUBSTRING(bits, 1, LEN(bits))
FROM
    Input

ミスった・・・

1
2
3
4
5
6
7
8
9
WITH
  Input(bits) AS (
    SELECT '0010001111101101'
  )
SELECT
    RIGHT(bits, 1)
      + SUBSTRING(bits, 1, LEN(bits) - 1)
FROM
    Input

テンプレートで。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <string.h>
#include <limits.h>

template<typename T>
void print2( T val )
{
  // 2進で表示するコード(省略)
}

template<typename T>
inline
T rotateShift( T val )
{
  static const char shift = sizeof( T ) * 8 - 1;
  static const unsigned long long rotate = 1ULL << shift;
  return static_cast<T>(
    ( val & 1 ) ?  ( rotate | val >> 1 ) : ( val >> 1 ) );
}

int main()
{
  print2( 1 );
  print2( rotateShift( 1 ) );
  print2( 0x7fffffff );
  print2( rotateShift( 0x7fffffff ) );
  print2( 0x80000000 );
  print2( rotateShift( 0x80000000 ) );
  print2( 1LL );
  print2( rotateShift( 1LL ) );
  print2( 0x7fffffffffffffff );
  print2( rotateShift( 0x7fffffffffffffff ) );
  print2( 0x8000000000000000 );
  print2( rotateShift( 0x8000000000000000 ) );

  return 0;
}
32ビット幅整数で実装しました。

 $ groovy rotateshift.groovy
 10000000000000000000000000000000
  1000000000000000000000000000000
   100000000000000000000000000000
                   10001111101101
 10000000000000000001000111110110
  1000000000000000000100011111011
 10100000000000000000010001111101
 10000000000000000000000000000000
                                1
                               10
                   10001111101101
                  100011111011010
                 1000111110110100
                10001111101101000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Integer.metaClass.rotateRight = { n ->
  n = (n + 32) % 32
  (delegate << (32-n)) | (delegate >>> n)
}
Integer.metaClass.rotateLeft = { n ->
  delegate.rotateRight(32-n)
}

def testR(String data, int shift){
  println Integer.toBinaryString(((int)Long.parseLong(data,2)).rotateRight(shift)).padLeft(32)
}
def testL(String data, int shift){
  println Integer.toBinaryString(((int)Long.parseLong(data,2)).rotateLeft(shift)).padLeft(32)
}


testR("10000000000000000000000000000000", 0)
testR("10000000000000000000000000000000", 1)
testR("10000000000000000000000000000000", 2)
testR("00000000000000000010001111101101", 0)
testR("00000000000000000010001111101101", 1)
testR("00000000000000000010001111101101", 2)
testR("00000000000000000010001111101101", 3)

testL("10000000000000000000000000000000", 0)
testL("10000000000000000000000000000000", 1)
testL("10000000000000000000000000000000", 2)
testL("00000000000000000010001111101101", 0)
testL("00000000000000000010001111101101", 1)
testL("00000000000000000010001111101101", 2)
testL("00000000000000000010001111101101", 3)
32ビット幅整数で実装しました。

 $ groovy rotateshift.groovy
 10000000000000000000000000000000
  1000000000000000000000000000000
   100000000000000000000000000000
                   10001111101101
 10000000000000000001000111110110
  1000000000000000000100011111011
 10100000000000000000010001111101
 10000000000000000000000000000000
                                1
                               10
                   10001111101101
                  100011111011010
                 1000111110110100
                10001111101101000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Integer.metaClass.rotateRight = { n ->
  n = (n + 32) % 32
  (delegate << (32-n)) | (delegate >>> n)
}
Integer.metaClass.rotateLeft = { n ->
  delegate.rotateRight(32-n)
}

def testR(String data, int shift){
  println Integer.toBinaryString(((int)Long.parseLong(data,2)).rotateRight(shift)).padLeft(32)
}
def testL(String data, int shift){
  println Integer.toBinaryString(((int)Long.parseLong(data,2)).rotateLeft(shift)).padLeft(32)
}


testR("10000000000000000000000000000000", 0)
testR("10000000000000000000000000000000", 1)
testR("10000000000000000000000000000000", 2)
testR("00000000000000000010001111101101", 0)
testR("00000000000000000010001111101101", 1)
testR("00000000000000000010001111101101", 2)
testR("00000000000000000010001111101101", 3)

testL("10000000000000000000000000000000", 0)
testL("10000000000000000000000000000000", 1)
testL("10000000000000000000000000000000", 2)
testL("00000000000000000010001111101101", 0)
testL("00000000000000000010001111101101", 1)
testL("00000000000000000010001111101101", 2)
testL("00000000000000000010001111101101", 3)

Index

Feed

Other

Link

Pathtraq

loading...