# Bitwise Operation
###### Tags: `C`, `Bitwise`
###### References: [`1`](https://puremonkey2010.blogspot.com/2011/05/c-bitwise-operation.html),
---
## Functions
### `SHIFT LEFT <<`, `SHIFT RIGHT >>`
>這兩個運算子的功能主要是移動一個變數中的所有位元，位元向左 / 向右移動之後，最高位 / 最低位的位元會消失，最低位 / 最高位的位元補 0
```
5 << 1 = 10 <==> 00100 << 1 = 01010
5 << 2 = 20 <==> 00101 << 2 = 10100
5 >> 1 = 2 <==> 00101 >> 1 = 00010
5 >> 2 = 1 <==> 00101 >> 2 = 00001
```
:::info
**當全部位元向左移動一位時，會變成原來的兩倍，向左移動一位時，會變成原來的1/2倍。**
:::
---
### `AND &`
>`&` 的功能是將兩個變數對應的位元進行 `AND` 邏輯運算，然後產生新變數。用來判別位元是不是一也很方便。
```
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
```
**測試有多少位元的值＝1：**
```c
#include <stdio.h>
int main(){
int num = ***;
int digit = sizeof(num) * 8; // 待測數為幾位元
int count = 0;
//for(int i=1; i<=num; i=i*2){if(num & i) count++;}
for(int i = digit-1; i >= 0; i --) //略去高位0.
if(num &(1<<i)) count++;
printf("%d\n", count);
return 0;
}
```
```c
int mark_9th_bit(int n) // 標示第九位元的值
{
return n & (1 << 8);
}
```
---
### `OR |`
>`|` 的功能是將兩個變數對應的位元進行 `OR` 邏輯運算。
**例如：**
```
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
```
---
### `XOR ^`
>`^` 的功能是將兩個變數對應的位元進行 `XOR` 邏輯運算。==可以用來反轉某位元的值，也可以用來做簡單加密。==
```
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
```
**反轉某位元**
```c
int reverse_9th_bit(int n) // 反轉第九位元的值
{
return n ^ (1 << 8);
}
```
**不使用暫存變數（temporary variable）交換兩個相異變數**
```c
// a should not equal to b
a = a ^ b
b = a ^ b
a = a ^ b
```
**加密**
```c
#include <stdio.h>
int main(void) {
char ch = 'D';
printf("before encoding：%c\n", ch);
ch = ch ^ 0xC;
printf("after encoding：%c\n", ch);
ch = ch ^ 0xC;
printf("decoding：%c\n", ch);
return 0;
}
```
**OUTPUT**
```
before encoding：D
after encoding：H
decoding：D
```
---
### `NOT ~`
>`~` 的功能是顛倒一個變數每一個位元的 0 和 1。
```
~0 = 1
~1 = 0
~00101101 = 11010010
```
---
## Applications
- ### **整數變號**
```c
int negative(int x)
{
return ~x + 1; // -x;
}
```
- `NOT` 後 `+1` -> ==二補數== -> 正負變號
- ### **判斷奇偶**
```c
bool is_odd(int x)
{
return x & 1; // x % 2;
}
```
- 觀察最低位元是否為 `1`
- TRUE，奇數
- FALSE，偶數
- ### **整數取絕對值**
```c
int abs(int x)
{
// x < 0 ? -x : x;
// x >> 31 = 111...111 (如果x是負數) or 000...000 (如果x是正數)
// x ^ (x>>31) => 如果 x 為負數則將 x 的 0轉1, 1轉0, 如果 x 為正數, 則保持x 不變.
// (x ^ (x >> 31)) - (x >> 31) => 如果 x 為正數則 x-0=x , 如果 x 為負數則 ~x-(-1) = -x
return (x ^ (x >> 31)) - (x >> 31);
}
```
```c
#include <stdio.h>
long int labs(long int x)
{
int n = sizeof(x)*8 - 1; // how many digit - 1
return (x ^ (x >> n)) - (x >> n);
}
int main(){
long int num = -1556543547665469;
printf("%ld\n", labs(num));
return 0;
}
```
- ### **最低位元`1`**
```c
#include <stdio.h>
int lowest_bit_1(int x)
{
print_bin(x);
printf("\n");
print_bin(-x);
printf("\n");
return x & -x;
}
int main(){
int num = 1638;
printf("%d\n", lowest_bit_1(num));
}
```
==[**原理:**](https://stackoverflow.com/questions/12247186/find-the-lowest-set-bit)==
:::spoiler
```
number: 0000001101111000
complement: 1111110010000111
```
Then we add 1 to it.
```
number: 0000001101111000
complement: 1111110010000111
add 1: 1111110010001000
```
Note that if the rightmost bit is 1, this would create a carry which flips all 1s into 0s until a 0 is reached.
This number is now actually also the binary representation of -number.
```
number: 0000001101111000
complement: 1111110010000111
add 1: 1111110010001000
-number: 1111110010001000
```
We now take the bitwise & of number and -number.
```
number: 0000001101111000
-number: 1111110010001000
number & -number: 0000000000001000
```
:::
- ### 最高位元`1`
```c
//O(log n)
unsigned int hibit(unsigned int n) {
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return n - (n >> 1);
}
int main(){
int a = 145;
printf("%d\n", test(a));
}
```
```c
unsigned int hibit(unsigned int x)
{
unsigned int n;
while ( (x & (x - 1)) != 0 ) {
x &= (x-1);
}
return x;
}
```
- ### **判斷是不是 `2` 的次方**
```c
bool is_power_of_2(int x) {
return (x & -x) == x;
}
```
==**原理:**==
- 因為如果是二的次方，則從二進制觀察時，只會有一個 set bit (e.g. `0010 0000`)。
所以 `(x & -x)` 得到的最低位 set bit，若又等於 `x` 本身，則表示 `x` 只有一個 set bit，也就是 `x` 為二的次方數。
- ### **交換兩個 `int` 變數**
```c
void swap(int& x, int& y)
{
x = x ^ y; // x' = x ^ y
y = x ^ y; // y' = x' ^ y = x ^ y ^ y = x
x = x ^ y; // x = x' ^ y' = x ^ y ^ x = y
}
```
- ### **計算有幾個位元是`1`**
```c
int count_bits2(unsigned int n) {
int i=0;
for (; n != 0; n>>=1)
if (n & 1)
++i;
return i;
}
```
==**原理:**==
- 一直將變數 `right shift 1` 並 `AND 1`，若為 `TRUE` ，則 `++count`。
--
```c
unsigned char Cal_bit1_Num(int sample)
{
unsigned char Num = 0;
while (sample)
{
Num++;
sample = (sample - 1) & sample;
}
return Num;
}
```
- ### **顛倒位元順序**
- Common Solution:
```c
int reverse_bits(int x)
{
x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
return x;
}
```
==**解釋**==
:::spoiler
```
x = 0101 1011 0001
0x55555555 -> 0101 0101 0101 0101 0101 0101 0101 0101
0xaaaaaaaa -> 1010 1010 1010 1010 1010 1010 1010 1010
(x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa)
= 0010 1101 1000 & 0101 0101 0101 | 1011 0110 0010 & 1010 1010 1010
= 0000 0101 0000 | 1010 0010 0010
= 1010 0111 0010
0x33333333 -> 0011 0011 0011 0011 0011 0011 0011 0011
0xcccccccc -> 1100 1100 1100 1100 1100 1100 1100 1100
0x0f0f0f0f -> 0000 1111 0000 1111 0000 1111 0000 1111
0xf0f0f0f0 -> 1111 0000 1111 0000 1111 0000 1111 0000
0x00ff00ff -> 0000 0000 1111 1111 0000 0000 1111 1111
0xff00ff00 -> 1111 1111 0000 0000 1111 1111 0000 0000
0x0000ffff -> 0000 0000 0000 0000 1111 1111 1111 1111
0xffff0000 -> 1111 1111 1111 1111 0000 0000 0000 0000
```
:::
- Use `uint32_t`:
關於 `uint32_t` 定義可以查看以下
:::spoiler **<stdint.h>**
```c
/* Exact integral types. */
/* Signed. */
/* There is some amount of overlap with <sys/types.h> as known by inet code */
#ifndef __int8_t_defined
# define __int8_t_defined
typedef signed char int8_t;
typedef short int int16_t;
typedef int int32_t;
# if __WORDSIZE == 64
typedef long int int64_t;
# else
__extension__
typedef long long int int64_t;
# endif
#endif
/* Unsigned. */
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
#ifndef __uint32_t_defined
typedef unsigned int uint32_t;
# define __uint32_t_defined
#endif
#if __WORDSIZE == 64
typedef unsigned long int uint64_t;
#else
__extension__
typedef unsigned long long int uint64_t;
#endif
/* Small types. */
/* Signed. */
typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;
#if __WORDSIZE == 64
typedef long int int_least64_t;
#else
__extension__
typedef long long int int_least64_t;
#endif
/* Unsigned. */
typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;
#if __WORDSIZE == 64
typedef unsigned long int uint_least64_t;
#else
__extension__
typedef unsigned long long int uint_least64_t;
#endif
/* Fast types. */
/* Signed. */
typedef signed char int_fast8_t;
#if __WORDSIZE == 64
typedef long int int_fast16_t;
typedef long int int_fast32_t;
typedef long int int_fast64_t;
#else
typedef int int_fast16_t;
typedef int int_fast32_t;
__extension__
typedef long long int int_fast64_t;
#endif
/* Unsigned. */
typedef unsigned char uint_fast8_t;
#if __WORDSIZE == 64
typedef unsigned long int uint_fast16_t;
typedef unsigned long int uint_fast32_t;
typedef unsigned long int uint_fast64_t;
#else
typedef unsigned int uint_fast16_t;
typedef unsigned int uint_fast32_t;
__extension__
typedef unsigned long long int uint_fast64_t;
#endif
/* Types for `void *' pointers. */
#if __WORDSIZE == 64
# ifndef __intptr_t_defined
typedef long int intptr_t;
# define __intptr_t_defined
# endif
typedef unsigned long int uintptr_t;
#else
# ifndef __intptr_t_defined
typedef int intptr_t;
# define __intptr_t_defined
# endif
typedef unsigned int uintptr_t;
#endif
/* Largest integral types. */
#if __WORDSIZE == 64
typedef long int intmax_t;
typedef unsigned long int uintmax_t;
#else
__extension__
typedef long long int intmax_t;
__extension__
typedef unsigned long long int uintmax_t;
#endif
.
.
.
```
https://sites.uclouvain.be/SystInfo/usr/include/stdint.h.html
:::
```c
uint32_t reverseBits(uint32_t n){
uint32_t m = 0;
for(int i=0; i<32; i++, n>>=1){
m <<= 1;
m |= n&1;
}
return m;
}
```
- ### 改某個`bit`為`1`或`0`
```c
void bit_ctrl_0 (char* pflag, int bit) {
*pflag &= ~(1 << bit); //改0 -> 先用mask，再用and
}
void bit_ctrl_1 (char* pflag, int bit) {
*pflag |= (1 << bit); //改1 -> 直接or
}
```
Sign in with Wallet
Connect another wallet