Bitwise Operation

Tags: `C`, `Bitwise`

References: `1`,

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

當全部位元向左移動一位時，會變成原來的兩倍，向左移動一位時，會變成原來的1/2倍。

`AND &`

& 的功能是將兩個變數對應的位元進行 AND 邏輯運算，然後產生新變數。用來判別位元是不是一也很方便。

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

測試有多少位元的值＝1：

#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;
}

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

反轉某位元

int reverse_9th_bit(int n) // 反轉第九位元的值
{  
    return n ^ (1 << 8);  
}

不使用暫存變數（temporary variable）交換兩個相異變數

// a should not equal to b
a = a ^ b
b = a ^ b
a = a ^ b

加密

#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

整數變號

int negative(int x)  
{  
    return ~x + 1;  // -x;  
}

NOT 後 +1 -> 二補數 -> 正負變號

判斷奇偶

bool is_odd(int x)  
{  
    return x & 1;   // x % 2;  
}

觀察最低位元是否為 1
- TRUE，奇數
- FALSE，偶數

整數取絕對值

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);  
}

#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`

#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));
}

原理:

          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`

//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));
}

unsigned int hibit(unsigned int x)
{
  unsigned int n;
  while ( (x & (x - 1)) != 0 )  {
      x &= (x-1);
  }
  return x;
}

判斷是不是 2 的次方
```
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` 變數

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`

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。

–

unsigned char Cal_bit1_Num(int sample)
{
    unsigned char Num = 0;

    while (sample)
    {
        Num++;
        sample = (sample - 1) & sample;
    }

    return Num;
}

顛倒位元順序

Common Solution:

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;  
}

解釋

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 定義可以查看以下

<stdint.h>

/* 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

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`

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
}

Bitwise Operation

Tags: C, Bitwise

References: 1,

Functions

SHIFT LEFT <<, SHIFT RIGHT >>

AND &

OR |

XOR ^

NOT ~

Applications

整數變號

判斷奇偶

整數取絕對值

最低位元1

最高位元1

判斷是不是 2 的次方

交換兩個 int 變數

計算有幾個位元是1

顛倒位元順序

改某個bit為1或0

Read more

**Hsuan's - Notes**

EASY