bit演算で値挿入

問題

最大32bit整数N, Mが与えられたときにNのjビット目からiビット目にMを挿入する。

考え方

Nのjからiビットを0に変えて、Mを挿入する

注意

ビットは0から数える。一番右が0ビット目。

コード例

#include<iostream>
#include<bitset>
using namespace std;

unsigned int insert(int i, int j, unsigned int N, unsigned int M){
    /*
    Nのiからj　bitにMを挿入する
    1, j ~ i bitの間をクリアする。 and する。
    2. j ~ iに　Mを入れる. or でできる
    */
    unsigned int clear, temp;
    // all 1 flg done
    clear = ~0;
    // j bit以下を0にする
    temp = ~0;
    temp >>= (sizeof(int)*8 - j-1);
    clear = clear & ~temp;
    // ibit以下を1にする
    temp = ~0;
    temp >>= (sizeof(int)*8 - i);
    clear = clear | temp;
    //---bitmask作り方改善-------------
    // unsigned int mask, right, left;
    // left = ~0;
    // left >>= (sizeof(int)*8 - j-1);
    // right = ~0;
    // right <<= i;
    // mask = right & left;
    // cout << bitset<32>(mask) << endl;

    // 1の操作
    N = N & clear;
    // 2の操作
    M <<= i;
    N = N | M;
    return N;
}

int main(void){
    unsigned int N = 0b10000000000;
    unsigned int M = 0b10011;
    int i,j ;
    i = 2;
    j = 6;
    N = insert(i, j, N, M);
    cout << bitset<32>(N) << endl;
    return 0;
}

参考

問題は以下から。

CRACKING the CODING INTERVIEW - Home