移位运算
一个简单的面试题目-竟然花了半天时间
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）可以很好的实现。
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息