この章について

「ビット操作」というタイトル章です。0と1ばっかり出てきます。
ビット操作を知らなくても割と問題は解けるみたいだけど知っておくと速かったりするらしい。

基本操作

a&b //AND
a|b  //OR
~a //NOT
a^b //XOR

//算術ビットシフト(符号は保存する)
a << b //aをb桁左にビットシフト
a >> b //aをb桁右にビットシフト

//論理ビットシフト(符号に関するビットごとずらす)
a <<< b 
a >>> b

Question 5-1

最大32ビットの整数$N$と$M$、ビットの位置を指す値$i$と$j$が与えられています。このとき、$N$の$j$ビット目から&i&ビット目に$M$を挿入するメソッドを書いてください。ただし、$j$と$i$の幅は$M$のビット数と一致していると仮定してかまいません。つまり、$M=10011$であれば$j$と$i$の幅は5と仮定してかまいません。$j=3$、$i=2$のような、$M$の幅と合わないような場合は考えなくてもかまわないということです。
例
入力 : N = 10000000000, M =10011, i = 2, j = 6
出力 : N = 10001001100

問題文にはなかったけど流石に$M \le N$ということで。
やりたいこと : $N$の$i$桁目から$j$桁目のビットを全部0にして、$i$桁ビットシフトした$M$を足せば目標の数になる。
$\rightarrow$ $i$桁目から$j$桁目のビットを全部0にする操作が難しいので工夫が必要

5-1.cpp

int insertMtoN(int n,int m,int i,int j){
    if(i > j){swap(i,j);}
    if(m > n){swap(m,n);}
    m <<= i;
    int lim = numeric_limits<int>::max();//ビット全部を1埋めた数(この値は2147483647)
    int left = lim << (j+1);//j桁目から
    int right = ((1<<i)-1);//i桁目までを0にしたいので
    left |= right;//この2数のORを取るとi桁目からj桁目以外のビットが1になった数を得られる
    n &= left;//ANDを取ることでnのi桁目からj桁目が0になる
    n |= m;
    return n;
}

Question 5-2

0から1までの実数値がdouble型として与えられるとき、それを2進数表記で出力してください。32文字以内で正確に表現できない場合は"ERROR"と出力してください。

32文字の中に小数点と1の位の0の2文字を含むのかは気になるが、キリが良いので小数点以下32桁ということに。
受験算数の2進数変換とかが思い出された。懐かしい。

dを最大32回ビットシフトしていって、1以上になるたびに1を引く。このとき、その位のビットは1だということもわかるので順に格納していく。
操作が終わってもdが0でなければ、32桁以内の小数で書けないことになるのでERROR。

5-2.cpp

void BinaryDouble(double d){
    int ord = 0,bit[32];//bit[32]の中に各位のbitの情報を格納
    if(d>=1.0 || d<=0){cout<<"ERROR"<<endl;}
    else{
        while(ord < 32){
            d*=2.0;
            if(d>=1.0){d-=1.0;bit[ord]=1;}
            else{bit[ord]=0;}
            ord++;
            if(d==0.0){break;}//0になったらループを出てよい
        }
        if(d!=0.0){cout<<"ERROR"<<endl;}
        else{
            cout<<0<<'.';
            for(int i=0;i<ord;i++){
                cout<<bit[i];
            }
            cout<<endl;
        }
    }
}

Question 5-3

ある整数があり、その中の1ビットだけ0から1に反転することができます。このような操作を行うとき、1の並びが最も長いときの長さを求めるコードを書いてください。
例
入力 : 1775 (2進 : 11011101111)
出力 : 8

(例の場合は下から5桁目を1にすることで1が8桁連続するようにできて、これが最大)

<愚直>
ビット表現に現れる0と1の個数をlistなりvectorなりにpushして、マージできそうなところはマージしてmaxを計算する
例の場合だと下から、1が4つ、0が1つ、1が3つ、0が1つ、1が2つ、という順で並んでいるので、vector = {4, 1, 3, 1, 2}になる。

<もうちょっとマシな解法>
結局マージするのは1が並ぶ2区間だけなので、その2つの区間にそれぞれ1がいくつ並んでいるかだけ保持しておけば良さそう。
$\rightarrow$ 変数prevとnowを用意して、prevを直前に数えた1の列の長さ、nowを今数えている1の列の長さとする。

5-3.cpp

int MaxLen(int n){
    int prev = 0,now = 0,zeroLen = 0,maxLen = 1;
    if((n&(n+1))==0){
        int ret = 0;
        while(n){
            ret++;
            n>>=1;
        } 
        return ret;
    }
    while(n){
        if(n&1){now++;}
        else if((n&1)==0){
            prev = ((n&2==0) ? 0 : now);
            now = 0;
        }
        maxLen = max(maxLen, prev + now + 1);
        n>>=1;
    }
    return maxLen;
}

Question 5-4

正の整数が与えられたとき、2進表現したときの1の個数が同じ整数の中で、1つ後の数と前の数を求めてください。

日本語が紛らわしいので、与えられた数を$n$としたとき
1つ後の数 $\rightarrow$ 条件を満たす数で、$n$より大きい方
1つ前の数 $\rightarrow$ 条件を満たす数で、$n$以下の方(場合によっては$n$より小さいものが存在しないのでその時は&n&を返す)
ということにする。

<愚直>
全探索。やめましょう。

<マシな解法>
具体的な操作を考える。
共通の思考として、大抵の場合前後の数は$n$とそう遠くない値のはずなので、なるべく下の方の桁をいじりたい。

2進表記した時に、なるべく下の方の桁にある"10"を"01"にできると嬉しい(逆もまた然り)
"10"を"01"にしたとき、それより下の桁では1をどう並べようと$n$より小さくなるので、残った1はなるべく上に並べたい
"01"を"10"にしたときは、それより下の桁に残った1はなるべく下に並べると値が小さくなって良い。

つまり、$n$の末尾にある111...000という塊だけに注目して、これの操作を考えると良い。

例えば $n = 110011100111000_{(2)}$ とする。前後の数をそれぞれprev, nextとすると、2進表記でそれぞれ
$110011100110100 = prev$
$110011100111000 = n$
$110011101000011 = next$
となる。

色をつけると、
$ 11001110011$$01$$00 = prev $
$110011100$$111$$000 = n$
$11001110$$1000011$ $= next$
緑色に塗った1付近しか変化していないのがわかる。
prevでは緑の1の最下位の1のみを1つ右にシフトしていて、nextでは緑の1を1つだけシフトして、残りの1は右に詰めている。
実装は以下。

5-4.cpp

int getNext(int n){
    if(n<=0){return -1;}
    int a = 1, zeroCount = 0, oneCount = 0;
    while((n&a) == 0){
        zeroCount++;
        a <<= 1;
    }
    while((n&a) > 0){
        oneCount++;
        a <<= 1;
    }
    if(zeroCount + oneCount == 31 || zeroCount + oneCount == 1){
        //111...000型で31桁だと次の数が得られない。また、n = 0でも次の数は存在しない
        return -1;
    }
    //(zeroCount + oneCount)桁以下を一旦全て0にして、末尾(oneCount)桁を1にする。
    n |= a;
    n&=(~(a-1));
    oneCount--;
    int b = (1<<oneCount) - 1;
    n|=b;
    return n;
}

int getPrev(int n){
    if(n<=0||(n&(n+1))==0){return -1;}//nが2^m-1型の整数だと1しか並ばないので後ろの式によって除外
    int a = 1, zeroCount = 0, oneCount = 0;
    //今度は0の個数から数える
    while((n&a) > 0){
        oneCount++;
        a <<= 1;
    }   
    while((n&a) == 0){
        zeroCount++;
        a <<= 1;
    }
    //こちらもgetNextと同様に特定の桁以下を全て0にした上で、(zeroCount + oneCount)桁目から下に 
    //(oneCount + 1)個の1を埋めた数を作って、最後にnとくっつける
    a <<= 1;
    a -= 1;
    a = ~a;
    n &= a;
    oneCount++;
    int b = (1<<oneCount) - 1;
    b <<=(zeroCount - 1);
    n|=b;
    return n;
}

Question 5-5

コード($n$ & ($n-1$) $==$ 0)について説明してください。

結論から述べると$n$が2冪ならtrue,そうでなければfalse。
証明は簡単で、$n$を2冪とすると $ n_{(2)} = 100...000, (n-1)_{(2)} = 11...111 $と書けるので、2数のANDを取ると0になる。
逆に$n$を2冪でないとすると、$n$の2進表記の最上位以外に1箇所以上の1が現れるので、$n$と$n-1$の桁数は等しくなる。なので少なくとも$n$ & ($n-1$) $!=$ 0 が成立する。

Question 5-6

ある整数$A$から$B$に変換するのに必要なビット数を決定する関数を書いてください。

XORを取れば2数のビットが異なる部分だけが浮き彫りになってくれるので、これでよさそう。

5-6.cpp

int changeAtoB(int a,int b){
    int ret=0;
    a^=b;
    for(int c=a;c!=0;c = c>>1){
        ret += c&1;
    }
    return ret;
}

しかしもう少し改善できて、関数内のfor文を

for(int c=a;c!=0;c = c>>1){
    ret += c&1;
}

から

for(int c=a;c!=0;c&=(c-1)){
    ret++;
}

にすると良い。上の方法では1桁ずつ見ているのでいらない部分も数えることになる。
実は下の方法は、ビットが立っている部分だけをダイレクトに数えていることになる。
Question5-5では、$n$ & ($n-1$)が2冪かどうかを判別していたが、これを応用すると$n$の一番小さい2冪の部分が$n$ & ($n-1$)の操作によって消えてくれることがわかる。2進数表示の形を考えれば、これが最前の数え方であることがわかった。

Question 5-7

偶数ビットと奇数ビットを、できるだけ少ない操作で入れ替えるプログラムを書いてください(たとえば、0ビット目と1ビット目、2ビット目と3ビット目を入れ替えます)。

2進表記の桁数が奇数の場合は、最上位に0があるものとして操作をする。
偶数桁目と奇数桁目の情報をそれぞれ保持しておいて、それぞれをビットシフトしたものの和を取ると良さそう。

5-7.cpp

int switchBits(int n){
    int odd = 1, even = 2;//oddに下から数えて奇数桁目、evenに偶数桁目のビットを保持する。
    //101010...0101を作る
    while(odd < n){
        odd <<= 2;
        odd += 1;
    }
    //1010...1010を作る
    while(even < n){
        even <<= 2;
        even += 2;
    }
    //偶数桁目、奇数桁目がそれぞれ残る
    odd &= n;
    even &= n;
    //oddを左に、evenを右にシフトすると桁が入れ替えられる。
    odd <<= 1;
    even >>= 1;
    return odd|even;
}

Question 5-8

モノクロのスクリーンが1次元のバイト型配列として保持されています。1バイトには連続した8ピクセルを保持することができます。スクリーンの幅は8の倍数で、バイトの途中で切れるような形にはなっていないことにします。当然ですが、スクリーンの高さは配列のサイズとスクリーンの幅から計算することができます。このとき、($x_1$,$y$)から($x_2$,$y$)まで水平な直線を描く関数を実装してください。
メソッドのシグネチャは以下のようにします。
drawLine(bite[] screen, int width, int $x_1$, int $x_2$, int y)

~~え、これは何。coming soon...~~