位元操作

發表於 | 分類於 ，

題目

  • 136 Single Number (Easy)

  • 137 Single Number II (Medium)

  • 260 Single Number III (Medium)

  • 268 Missing Number (Easy)

  • 389 Find the Difference (Easy)

  • 190 Reverse Bits (Easy)

  • 191 Number of 1 Bits (Easy)

  • 231 Power of Two (Easy)

  • 405 Convert a Number to Hexadecimal (Easy)

  • 342 Power of Four (Easy)

  • 326 Power of Three (Easy)

  • 1009 Complement of Base 10 Integer (Easy)

  • 371 Sum of Two Integers (Medium)

  • 397 Integer Replacement (Medium)

  • 89 Gray Code

  • 461 Hamming Distance

  • 1342 Number of Steps to Reduce a Number to Zero

  • 868 Binary Gap

  • 1486 XOR Operation in an Array

  • 1720 Decode XORed Array

  • 476 Number Complement

  • 201 Bitwise AND of Numbers Range

[補充]

  • 2119 A Number After a Double Reversal

  • 338 Counting Bits

  • 7 Reverse Integer

  • 29 Divide Two Integers (Medium)

  • 67 Add Binary (Easy)

  • 387 First Unique Character in a String (Easy)

  • 1356 Sort Integers by The Number of 1 Bits (Easy)

  • 693 Binary Number with Alternating Bits (Easy)

  • 762 Prime Number of Set Bits in Binary Representation (Easy)

without

  • 兩數字相加，但硬體不支援+ -
    1
    2
    3
    4
    5
    6
    7
    int getSum(int a, int b) {
        while(a){
            int carry = (a&b&0x7fffffff)<<1, sum = a^b;
            a = carry, b = sum;
        }
        return b;
    }
  • 一數字是否為三的倍數，但硬體不支援* /
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int input = 12;
    int remainder = 0;
    while(input != 0){
        remainder += input & 0x3;
        input = input>>2;
        if(input == 0 && remainder >= 3){
            input = remainder-3;
            remainder = 0;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // binary search
    bool multipleOf3 (int n){
        int l = 0 ;
        int h = n ;
        while(h-l>1){
            int m = l + (h-l)/2 ;
            if (3*m <= n) l = m ;
            else h = m ;
        }
        return 3*l == n ;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // bit Manipulation 
    // log(n)
    bool IsThreesMultiple(int number) {
    	if (number < 10)
    		return number == 0 || number == 3 || number == 6 || number == 9;
    	int oddSums = 0, evenSums = 0;
    	for (int i = 31; i >= 0; i--)
    		if (i & 1)
    			oddSums += (number & (1 << i) ? 1 : 0);
    		else
    			evenSums += (number & (1 << i) ? 1 : 0);
    	return IsThreesMultiple(oddSums - evenSums >= 0 ? oddSums - evenSums : evenSums - oddSums);
    }

  • 從兩個數字中找出最大的一個而不使用判斷描述
    1
    2
    3
    4
    int max(int a, int b)
    {
        return ((a + b) + abs((a - b))) / 2;
    }
  • 整數變號
    1
    2
    3
    4
    5
    6
    7
    8
    void negative(int& x)
    {
        return ~x + 1;          // -x;
    }
    void negative(int& x)
    {
        return (x ^ -1) + 1;    // -x;
    }

技巧

  • 善用xor a^a=0 a^0 = a，且滿足交換率。1720
  • a^a=0 a^0 = a 可以抓出陣列中唯一出現一次的元素，其餘出現兩次。136
  • ret ^= i ^ *(nums + i); 0~n 陣列中哪個數字是
  • n = n & (n - 1); 可以用來找 n在二進位有多少個1 191, 231
  • 0~n 陣列中 標記陣列中拜訪過元素為負數，就可以知道哪個數字重複了
  • 快慢指針，如果有重複的值會被找出，且不會修改陣列元素

leetcode

hackerrank

Bit Manipulation

Lonely Integer

1
2
3
4
5
int lonelyinteger(int a_count, int* a) {
    int ret = 0;
    for(int i=0;i<a_count;++i) ret^=a[i];
    return ret;
}

Maximizing XOR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maximizingXor(int l, int r) {
    int ret = 0;
    for(int i=l;i<=r;++i){
        for(int j = l;j<=r;++j){
            int xor= i^j;
            ret = max(ret, xor);
        }
    }
    return ret;

    // option 2 
    int xor = l^r, mx =0;
    while(xor){
        mx |= xor;
        xor>>=1;
    }
    return mx;

}

Counter game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char* counterGame(unsigned long long int n){
    int count = 0;
    // the count of reducing the power of 2 to 1
    while (n > 0 && n % 2 == 0) {
            n /= 2;
            count++;
    }
    // the count of reducing a number to the power of 2
    while (n > 0) {
            if (n % 2 == 1) {
                count++;
            }
            n >>= 1;
    }
    if (count % 2 == 1) {

       return "Richard";
    } else {
        return "Louise";
    }   
}

Xor-sequence

Sum vs XOR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long sumXor(long n) {
    // option 0 => time out
    // long ret = 0;
    // for(long i =0;i<=n ;++i){
    //     if( (n+i) == (n^i)) ret++;
    // }
    // return ret;
    
    // option 1 bit manipulation
    // find the number of zeros in binary repr.
    // Arrangement and Combine
    long ret = 0;
    while(n>1){
        
        if((n&1) ==0)ret++;
        n >>=1;
    }
    return pow(2,ret);
}

The Great XOR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long theGreatXor(long x) {
    
    // option 0 time out 
    // long ret = 0.0;
    // for(long i=1;i<x ;++i){
    //     if( (x^i) > x) ret++;
    // }
    // return ret;
    
    // option 1 bit manipulation
    long ret = 0;    
    int b =0;
    while(x){
        // this bit is zeros
        if((x&1)==0) ret += (1L<<b);
        b++;
        x>>=1;
    }
    return ret;
}


Yet Another Minimax Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void nextPermutation(int n, int *a) {
    int k;
    for(k =n-2 ;k>-1 ;k--){
        if(*(a+k) < *(a+k+1)) break;
    }
    if(k<0){
        //reverse the whole arr
        int i=0,j=n-1;
        while(i<j){
            // swap i j
            int temp = *(a+i);
            *(a+i) = *(a+j);
            *(a+j) = temp;
            i++;
            j--;          
        }
    }
    else{
        int l;
        for(l=n-1;l>k;l--){
            if(*(a+l) > *(a+k)) break;
        }
        // swap k l
        int temp = *(a+l);
        *(a+l) = *(a+k);
        *(a+k) = temp;
        
        //reverse k+1 to end
        int i= k+1, j=n-1;
        while(i<j){
            int temp = *(a+i);
            *(a+i) = *(a+j);
            *(a+j) = temp;
            i++;
            j--;
        }
    }
}
int numb(int n){
    if(n==1 ) return 1;
    int a = 1, c = a;
    for(int i=2;i<=n;++i){
        c = i *a;
        a =c;
    }
    return min(INT_MAX, c);
}
int anotherMinimaxProblem(int a_count, int* a) {
    // option 0 time out
    int count = numb(a_count);
    int ret = INT_MAX;
    while(count){
        count--;
        int score = 0;
        for(int i=0;i<a_count-1;++i){
            int temp = *(a+i)^ *(a+i+1);
            score = max(temp,score);
        }
        ret = min(score, ret);
        nextPermutation(a_count, a);
    }
    return ret;
}

Sansa and XOR

1
2
3
4
5
6
7
8
int sansaXor(int arr_count, int* arr) {
    if(arr_count%2==0) return 0;
    int ret = 0;
    for(int i=0;i<arr_count ; i+=2){
        ret ^= *(arr+i);
    }
    return ret;
}

AND Product

1
2
3
4
5
6
7
8
9
10
11
long andProduct(long a, long b) {
    // find leftmost bit & operation is 1 inn a&b bit array
    int i=0;
    while(a!=b){
        a >>=1;
        b >>=1;
        i++;        
    }
    return (b<<i);
}

Time Complexity: Primality

Bitwise Operators

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
string primality(int n) {
    
    
    // option 0 判斷多個 是否為質數
    if(n<2) return "Not prime";     
    vector<int> primes(n+1, true);
    for(int  i= 2;i<=n/i;++i){
        if(primes[i]){
            for(int j=i+i ; j<=n ;j+=i) primes[j] = false;
        }
    }   
    if(primes[n]) return "Prime";
    return "Not prime";


    // option 1 快速判斷一個數是否為質數
    if(n==1) return "Not prime";
    if(n==2 || n==3 || n==5 ) return "Prime";
    if(n%2==0 || n%3 ==0 || n%5 ==0  )  return "Not prime";
    for(int i=3;i<=n/i;++i){
        if(n%i==0) return "Not prime";
    }
    return "Prime";
}

十進制轉為二進制，並表示

1

面試題目

十進制轉為十六進制

  1. get-set-clear-inverse 第18位元的bit值

    set 一般set 是設定為1
    inverse = flip = Toggling

a. write a function to get bit18 value of an unsigned integer data and return 0 or 1
b. write a function to set bit18 value of an unsigned integer data
c. write a function to clear bit18 value of an unsigned integer data
d. write a function to inverse bit18 value of an unsigned integer data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int get(unsigned int n){
    return (n & (1<<17) );
}
void set(unsigned int &n){
    n = (n | (1<<17));
}

void clear(unsigned int &n){
    n = (n & ~(1<<17));
}

void inverse(unsigned int &n){
    n = (n^ (1<<17));
}

  1. union
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct BYTE_struct{
    unsigned char BYTE4;
    unsigned char BYTE3;
    unsigned char BYTE2;
    unsigned char BYTE1;
}
union LongFlag{
    unsigned long All;
    struct BYTE_struct BYTEMODE;
};
LongFlag flag;
flag.All = 0x1234567;
flag.BYTE_struct.BYTE1 = 0xFA;
flag.BYTE_struct.BYTE2 &= 0xAA;
flag.BYTE_struct.BYTE3 &= 0x55;
flag.BYTE_struct.BYTE4 = 0x11;

請問flag.All 的結果

fa224511

  1. 迴圈印出的數字 + 陷阱

    1
    2
    3
    4
    unsigned int i;
    for(i=10;i>=10 ; i--){
        printf("%d\n", i);
    }

    會印出負的數字，死回圈

  2. 解釋下列function功能

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 二進制中有多少個1
    int func(int x){
        int a = 0;
        while(x){
            a++;
            x = x&(x-1);
        }
        return a;
    }
    // 是否為２的次方
    bool func(unsigned int n){
        return (n&(n-1) ==0);
    }

  3. big and little endian + 指標

memory space value
0x1000 0x01
0x1001 0x23
0x1002 0x45
0x1003 0x67
0x1004 0x89
0x1005 0xAB
0x1006 0xCD
0x1007 0xEF 
1
2
3
4
5
unsigned int *ptr = 0x1000;
printf("%X", *ptr+1); 
// 0x67452302
printf("%X", *(ptr+1));  
// 0x89674523
  1. 指標
1
2
3
4
5
6
7
8
9
int a[] = {1,2,3,4,5,6};
int *p = a;
*(p++) += 100;  // 等同 *p++ += 100;
*(++p) += 100;

for(int i=0;i<6;++i){
    printf("%d\t", a[i]);
}
// 101  2   103 4   5   6
  1. 觀念 變數存活範圍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#define ARRAY_SIZE(20);

char * func_a(){

    int i ;
    char array_a[ARRAY_SIZE];

    for(i=0;i<ARRAY_SIZE;++i){
        array_a[i] = i;
    }

    return &array_a[0];
}

int main(void){
    char *buf_ptr = NULL;
    int i;
    buf_ptr = func_a();
    for(i=0;i<ARRAY_SIZE; ++i){
        printf("%d\n", buf_ptr[i]);
    }

    return 0;
}

// 函數返回，因陣列變數只存活於函數當中，所以返回時會釋放，所以再去取該記憶體位置會得到亂碼
// 可以改成用malloc或 new 在返回