# 位运算实用指南

#### 基础篇

```// C#
int multiply_2_power_n(int val, int n)
{
// val * (2 power n)
return val << n;
}

// C#
int divide_2_power_n(int val, int n)
{
// val / (2 power n)
return val >> n;
}```

```// C#
int get_bit(int val, int n)
{
// get val's n-th bit
return val & (1 << n);
}

// C#
int set_bit(int val, int n)
{
// set val's n-th bit to 1
return val | (1 << n);
}

// C#
int clear_bit(int val, int n)
{
// set val's n-th bit to 0
return val & (~(1 << n));
}```

```// C#
int update_bit(int val, int n, int s)
{
// update val's n-th bit to s (s should be 1 or 0)
return (val & (~(1 << n))) | (s << n);
}```

```// C#
int toggle_bit(int val, int n)
{
// toggle val's n-th bit
return val ^ (1 << n);
}```

```// C#
int clear_bits_to_n(int val, int n)
{
// clear bits from top(msb) to n
return val & ((1 << n) - 1);
}

// C#
int clear_bits_from_n_1(int val, int n)
{
// clear bits from n - 1 to 0(lsb)
return val & (~((1 << n) - 1));
}```

```// C#
int modulus_power_of_2(int val, int n)
{
// val % (2 power n)
return val & ((1 << n) - 1);
}```

#### 进阶篇

```// C#
bool is_even(int val)
{
// check whether val is even
return (val & 1) == 0;
}

// C#
bool is_odd(int val)
{
// check whether val is odd
return (val & 1) == 1;
}```

```// C#
int get_sign(int val)
{
// get val's sign
return (val >> 31) & 1;
}```

```// C#
int get_sign(int val)
{
// normal way to get val's sign
return val >= 0 ? 0 : 1;
}```

```// C#
bool is_power_of_2(int val)
{
// check whether val is power of 2
return (val & (val - 1)) == 0;
}```

```// C#
bool is_power_of_2(int val)
{
// check whether val is power of 2
return ((val & (val - 1)) == 0) && (val != 0);
}```

```// C#
int floor_power_of_2(int val)
{
// calc power of 2 which <= val
val |= (val >> 1);
val |= (val >> 2);
val |= (val >> 4);
val |= (val >> 8);
val |= (val >> 16);
return val - (val >> 1);
}```

```// C#
int ceil_power_of_2(int val)
{
// calc power of 2 which >= val
val -= 1;
val |= (val >> 1);
val |= (val >> 2);
val |= (val >> 4);
val |= (val >> 8);
val |= (val >> 16);
val += 1;
return val;
}```

```// C#
int closest_power_of_2(int val)
{
var ceil = ceil_power_of_2(val);
var floor = floor_power_of_2(val);
return val - floor < ceil - val ? floor : ceil;
}```

```// C#
int closest_power_of_2(int val)
{
var ceil = ceil_power_of_2(val);
var floor = ceil >> 1;
return val - floor < ceil - val ? floor : ceil;
}```

#### 更多篇

```// C#
int min(int a, int b)
{
var mask = (a - b) >> 31;
}

// C#
int max(int a, int b)
{
var mask = (a - b) >> 31;
}```

```// C#
int clamp(int val, int min_val, int max_val)
{
return min(max(val, min_val), max_val);
}```

```// C#
void swap(ref int a, ref int b)
{
a ^= b;
b ^= a;
a ^= b;
}```

abs函数的一个位运算版本(可以参考这里进一步了解):

```// C#
int abs(int v)
{
var mask = v >> 31;
}```

```// C#
int if_c_then_a_else_b(int c, int a, int b)
{
// c <= 0 means false, > 0 means true
return ((-c >> 31) & (a ^ b)) ^ b;
}```

```// C#
int if_c_then_a_else_0(int c, int a)
{
// c <= 0 means false, > 0 means true
return (-c >> 31) & a;
}```

```// C#
uint revert_bits(uint val)
{
val = ((val & 0x55555555) << 1) | ((val & 0xAAAAAAAA) >> 1);
val = ((val & 0x33333333) << 2) | ((val & 0xCCCCCCCC) >> 2);
val = ((val & 0x0F0F0F0F) << 4) | ((val & 0xF0F0F0F0) >> 4);
val = ((val & 0x00FF00FF) << 8) | ((val & 0xFF00FF00) >> 8);
val = ((val & 0x0000FFFF) << 16) | ((val & 0xFFFF0000) >> 16);
return val;
}```

```// C#
uint revert_bytes(uint val)
{
val = ((val & 0x00FF00FF) << 8) | ((val & 0xFF00FF00) >> 8);
val = ((val & 0x0000FFFF) << 16) | ((val & 0xFFFF0000) >> 16);
return val;
}```

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

http://graphics.stanford.edu/~seander/bithacks.html

113 篇文章22 人订阅

0 条评论

## 相关文章

### 计算字符串相似度算法——Levenshtein

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

8491

760

### R与数据分析学习总结之一：R语言基本操作

? 最近开始学习R语言，把学习笔记和小伙伴们分享一下吧，欢迎一起交流 R 起源： R是S语言的一种实现。S语言是由 AT&T贝尔实验室开发的一种用来进行数据探...

6206

3575

46612

1572

3465

2391

1211

1.8K5