d326: 程式設計師的面試問題(二)

2019-08-29

內容

位元運算常會有 machine dependant 的問題,
直接定義 1 byte = 8 bits, int 型態為 32 bits.

某甲碰到一個面試問題:

==============================================
輸入三個有號數 v, a, b,型態都是 int.
v 是介於-2147483647 到 2147483647 的整數值.
a 是代表這個整數的第 a 個 bit.
b 如果是 1,表示要將 v 的第 a bit 設成 1.
b 如果是 0,表示要將 v 的第 a bit 設成 0.

這個題目大意就是將 v 的第 a bit 設成 0 或 1.

請將程式運算的結果轉成二進位並輸出到螢幕上.

==============================================

某甲很快的 build 出大略的雛形如下:

#include <stdio.h>

/* set bit b to 1 */
int set_bit(int v, int b)
{

}

/* set bit b to 0 */
int unset_bit(int v, int b)
{

}

/* check_bit b is 1 or 0 */
int check_bit(int v, int a, int b)
{

}

int main(void)
{
    int i, v, bit, isSet;

    while(scanf("%d %d %d",&v,&bit,&isSet)==3)
    {
        if(isSet)
            v = set_bit(v, bit);
        else
            v = unset_bit(v, bit);

        for(i=31;i>=0;--i)
            printf( "%d", check_bit(v, 32, i) );
        putchar('\n');
    }


    return 0;
}

但是他還沒有把 function 完成.
現在請你完成這個程式,請嚴格要求自己每個 function 只用一行完成.
也就是每個 function 只有 return 運算;

當然,如果你有更快的做法也可以,只要通過 judge 的測資就可以了.

輸入

每行輸入三個有號整數,v, a, b, 用一個空白字元隔開.
v 的範圍為-2147483647 到 2147483647.
a 的範圍為 0 到 31.
b 不是 0 就是 1.
全部測資以 EOF 做為結束.

0 0 1
1 0 0
2147483647 31 1
-1 31 0
4 0 1
4 0 0

輸出

請對每一行測資輸出一行答案轉二進位數,也就是說會有 32 個整數,其整數不是 0 就是 1.
最左邊為最高位元, 最右邊為最低位元.
請參考範例測資和答案.

00000000000000000000000000000001
00000000000000000000000000000000
11111111111111111111111111111111
01111111111111111111111111111111
00000000000000000000000000000101
00000000000000000000000000000100

解題思路

位元運算題，

將 a 位元設成 b，而 b 有兩種情況

b = 1，先將要改變的位元設成 1，然後和 b 做 OR

v | (1 << a)
b = 0，先將要改變的位元設成 1，將該數用位元 NOT('~')使目標位元變成 0，其他位源都變為 1 後再和 b 做 AND

v & ~(1 << a)

改變好後用將第 32~1 位元依次右移到第 1 位元，再和 1 做 AND 使除了第 1 位元其他位源都變成 0，最後輸出答案即可。

完整程式碼

AC (2ms, 76KB)

#include <stdio.h>

int main()
{
    int v, a, b;
    while (scanf(" %d %d %d", &v, &a, &b) == 3)
    {
        v = b ? (v | (1 << a)) : (v & ~(1 << a));
        for (int i = 31; ~i; i--)
            putchar(((v >> i) & 1) + '0');
        putchar('\n');
    }
    return 0;
}