位元操作 - a920604a/leetcode GitHub Wiki

title: 位元操作 tags:
- Bit Manipulation categories: - CS - Data Structure comments: false

題目

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)

技巧

善用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

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

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

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

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

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

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

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

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

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

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

面試題目

十進制轉為十六進制

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

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

union

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

迴圈印出的數字 + 陷阱

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

會印出負的數字，死回圈

解釋下列function功能

// 二進制中有多少個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);
}

big and little endian + 指標

memory space	value
0x1000	0x01
0x1001	0x23
0x1002	0x45
0x1003	0x67
0x1004	0x89
0x1005	0xAB
0x1006	0xCD
0x1007	0xEF

unsigned int *ptr = 0x1000;
printf("%X", *ptr+1); 
// 0x67452302
printf("%X", *(ptr+1));  
// 0x89674523

指標

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

觀念變數存活範圍

#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 在返回