2595. Number of Even and Odd Bits

tags: Easy、Bitwise

You are given a positive integer n.
Let even denote the number of even indices in the binary representation of n with value 1.
Let odd denote the number of odd indices in the binary representation of n with value 1.
Note that bits are indexed from right to left in the binary representation of a number.
Return the array [even, odd].

解法:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* evenOddBit(int n, int* returnSize) {
    int* array = (int*)malloc(2 * sizeof(int));
    *returnSize = 2;
    int even = 0;
    int odd = 0;
    int i = 0;
    while (n != 0) {
        if ((n & 1) && (i % 2 == 0)) {
            even++;
        }
        else if ((n & 1) && (i % 2 == 1)) {
            odd++;
        }
        i++;
        n >>= 1;
    }
    array[0] = even;
    array[1] = odd;
    return array;
    
}

762. Prime Number of Set Bits in Binary Representation

tags: Easy、Bitwise

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.
Recall that the number of set bits an integer has is the number of 1's present when written in binary.
For example, 21 written in binary is 10101, which has 3 set bits.

解法1:

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }

    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}


int countPrimeSetBits(int left, int right) {
    int countPrime = 0;
    for (int i = left; i <= right; i++) {
        int count = 0;
        int temp = i;
        while (temp != 0) {
            if (temp & 1) {
                count++;
            }
            temp >>= 1;
        }
        if (isPrime(count) == 1) {
            countPrime++;
        }
    }
    return countPrime;
}

解法2: 使用int __builtin_popcount(x)

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }

    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}


int countPrimeSetBits(int left, int right) {
    int countPrime = 0;
    for (int i = left; i <= right; i++) {
        int n = i;
        int count = __builtin_popcount(n);
        if (isPrime(count)) {
            countPrime++;
        }
    }
    return countPrime;
}

__builtin_popcount 是一個 GCC（GNU Compiler Collection）提供的內建函式，用來計算一個整數的二進位表示中有多少個位元（bit）被設為 1。這個函式可以有效地計算一個數字的「1 的位數」，也就是所謂的「popcount」（population count）。

1356. Sort Integers by The Number of 1 Bits

tags: Easy、Bitwise

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.
Return the array after sorting it.

解法1:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int countBits(int n) {
    int x = n ;
    int bits = 0;
    while (x != 0) {
        if (x & 1) {
            bits++;
        }
        x >>= 1;
    }
    return bits;
}

int* sortByBits(int* arr, int arrSize, int* returnSize) {
    int bitsNum = 0;
    *returnSize = arrSize;
    for (int i = 0; i < arrSize-1; i++) {
        for (int j = 0; j < arrSize-i-1; j++)
            if (countBits(arr[j]) > countBits(arr[j+1])) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            else if (countBits(arr[j]) == countBits(arr[j+1])) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
    }
    return arr;
}

解法2:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int compare(const void *a, const void *b) {
    int bitsA = __builtin_popcount(*(int*)a);
    int bitsB = __builtin_popcount(*(int*)b);

    return (bitsA == bitsB) ? ((*(int*)a) - (*(int*)b)) : (bitsA - bitsB);
}

int* sortByBits(int* arr, int arrSize, int* returnSize) {
    *returnSize = arrSize;
    qsort(arr, arrSize, sizeof(int), compare); 
    return arr;
}