移位运算

一个简单的面试题目-竟然花了半天时间

2012-04-04 21:07 by pingjiang, 1178 visits, 收藏, 编辑

一个简单的面试题目-竟然花了半天时间才调试通。一方面是因为水平有限，另一方面就是对移位运算不是非常的了解。如果你也不是很了解移位运算，这是一个很好的学习的机会。

面试题

参考：http://topic.csdn.net/u/20080823/00/f2597efb-f00d-4ec6-9c6e-ecfe3f003f59.html

6. You have an array of 4 32-bit integers which you use to store a 128-bit number. Fill in the following functions for bitwise shifting operations.

uint32 storage[4]; （大致的意思是：对一个数组移位运算）

一个简洁但是错误的答案（至少有一点，当count>32时就有问题了）

void ShiftLeft(int count)
{
    unsigned int temp = 0;
    for(int i = 0; i < 4; ++i)
    {
        storage[i] = storage[i] << count | temp;
        temp = storage[i] >> sizeof(unsigned int)*8 - count;
    }
}
bool ShiftRight(int count)
{
    unsigned int temp = 0;
    for(int i = 3; i >= 0; --i)
    {
        storage[i] = storage[i] >> count | temp;
        temp = storage[i] << sizeof(unsigned int)*8 - count;
    }
}

我的实现如下所示。默认使用小端序，这样便于处理，还有就是print的时候先输出低位，后输出高位。

虽然没有通过完全的测试，但是程序的逻辑应该没有问题的。

考虑到复用和可读性，这里使用了大量的宏，如果你有什么更好的建议，希望你能告诉我。

#include <stdio.h>
 
typedef unsigned int u32;
 
//               0     1      2      3
// 假设使用小端序0-31, 32-63, 64-95, 96-127
#define N 4
u32 data[N] = { 0x000000FF, 0x0000FF00, 0x00FF0000, 0xFF000000 };
 
#define bit_get(num, i) ( ((num) >> i) & 1 )
#define bit_set1(num, i) do { num |= (1 << (i)); } while(0)
#define bit_set0(num, i) do { num &= ( ~(1 << (i)) ); } while(0)
#define data_bit(i) ( bit_get(data[(i) / 32], (i) % 32) )
#define data_set1(i) bit_set1(data[(i) / 32], (i) % 32)
#define data_set0(i) bit_set0(data[(i) / 32], (i) % 32)
 
#define bit_low(n) (u32)( (1 << (n)) -1 )
#define bit_high(n) (u32)( bit_low(n) << (32 - (n)) )
#define shift_left(num, n) ( (num) << (n) )
#define shift_right(num, n) ( (num) >> (n) )
#define shift_left_out(num, n) ( (num) & bit_low(n) )
#define shift_right_out(num, n) ( (num) & bit_high(n) )
#define pad_low(out, n) ( (out) << (32 - (n)) )
#define pad_high(out, n) ( (out) >> (32 - (n)) )
 
#define u32_bits() (sizeof(u32) * 8)
 
void data_not() {
    u32 i, len = 32 * N;
    for(i=0;i<len;i++) {
        if(data_bit(i) == 0) { 
            data_set1(i); 
        } else { 
            data_set0(i);
        }
    }
}
 
void data_shift_left(int n) {
    u32 i,j;
    for(j=0;j<n;j++) {
        for(i=1;i<N-j;i++) {
            data[i-1] = data[i];
        }
        data[N-1-j] = 0;
    }
}
 
void data_shift_right(int n) {
    u32 i,j;
    for(j=0;j<n;j++) {
        for(i=N-1;i>j;i--) {
            data[i] = data[i-1];
        }
        data[j] = 0;
    }
}
 
u32 data_bit_shift_left(int n) {
    int i;
    u32 div = n / u32_bits(), out, last_out = 0;
    n %= u32_bits();
    if(div > 0) {
        data_shift_left(div);
        return data_bit_shift_left(n);
    } else {
        for(i = N-1; i >= 0; i--) {
            out = shift_left_out(data[i], n);
            data[i] = (data[i] >> n) | pad_low(last_out, n);
            last_out = out;
        }
    }
    return last_out;
}
 
u32 data_bit_shift_right(int n) {
    int i;
    u32 div = n / u32_bits(), out, last_out = 0;
    n %= u32_bits();
    if(div > 0) {
        data_shift_right(div);
        return data_bit_shift_right(n);
    } else {
        for(i = 0; i < N; i++) {
            out = shift_right_out(data[i], n);
            data[i] = (data[i] << n) | pad_high(last_out, n);
            last_out = out;
        }
    }
    return last_out;
}
 
void data_bit_print() {
    int i;
    u32 len = u32_bits() * N;
    for(i=0;i<len;i++) {
        if(i % u32_bits() == 0) { printf("\n"); }
        printf("%d", data_bit(i));
    }
    printf("\n");
}
 
int main(int argc, char *argv[]) {
    data_bit_print();
    data_bit_shift_left(120);
    data_bit_print();
 
    return 0;
}

移位运算的总结

1、在C/C++中对负数与或非，移位运算会出现什么结果呢？比如：（-2） & 65535 = ？

通过GCC编译发现结果为0xfffe,可能是因为0xfffe & 0xffff = 0xfffe,其实，这里我还有一个疑问：这里的类型是如何来转换的，-2如果转换为int32类型就不是这样的结果了。

2、如果来获取比特位，或者设置比特位的值。使用上面的几个宏（bit_get,bit_set0,bit_set1）可以很好的实现。