Giới thiệu

Đây là trích bài giảng trong khoá học Luyện thi chứng chỉ công nghệ thông tin Nhật Bản https://fe.techmaster.vn: các kỹ thuật thao tác với Bit.

Bit Manipulation

Kiểm tra lowest bit (bit có giá trị thấp nhất)

Sử dụng toán tử AND theo bit (&) để kiểm tra bit thấp nhất của một số. Biểu thức (num & 1) sẽ trả về 1 nếu bit thấp nhất được đặt (tức là số lẻ) và 0 nếu bit thấp nhất không được đặt (tức là số chẵn).

int num = 5;
if ((num & 1) == 1) {
    System.out.println(num + " is odd");
} else {
    System.out.println(num + " is even");
}
java

Nhân 2x2^x2x một số

Sử dụng toán tử dịch trái << x với x số bước dịch.

int num = 3;
int result = num <<  2; // 3 * 2 * 2
System.out.println(result); //12
java

Chia một số cho 2x2^x2x

Sử dụng toán tử dịch phải >> để chia một số cho hai. Biểu thức num >> 1 sẽ dịch chuyển các bit của số sang phải một vị trí, chia đôi rất hiệu quả về tính toán

int num = 8;
int result = num >> 1;
System.out.println(result);
java

Đoạn code trên in ra 4 là 8/2=4

Chú ý chia bằng dịch bit chỉ hoạt động với các số dương. Nếu bạn cố chia một số âm cho hai, thì bit dấu cũng sẽ bị dịch chuyển, dẫn đến giá trị không chính xác. Trong trường hợp đó, hãy sử dụng num = num/2

Kiểm tra giá trị bit ở một vị trí cụ thể (Bit Masking)

Cách nay tương tự như “Kiểm tra lowest bit”, khác ở chỗ bit cần kiểm tra ở vị trí thứ n
Hãy tạo một bit mask bằng 1 << n

if ((num & (1 << n)) != 0) {
    // bit at position n is set
} else {
    // bit at position n is not set
}
java

Ví dụ chi tiết

int num = 5; // binary: 101
int bitToCheck = 2;
if ((num & (1 << bitToCheck)) != 0) {
    System.out.println("Bit at position " + bitToCheck + " is set in " + num);
} else {
    System.out.println("Bit at position " + bitToCheck + " is not set in " + num);
}
java

Dựng bit ở một vị trí cụ thể (Bit Setting)

Sử dụng toán tử OR | để đặt một bit vị trí n trong một số num

num = num | (1 << n);
java

Ví dụ chi tiết

int num = 5; // binary: 101
int bitToSet = 2;
num = num | (1 << bitToSet);
System.out.println("Number after setting bit at position " + bitToSet + " : " + num);
java

Xoá bit ở một vị trí cụ thể (Bit Clearing)

Sử dụng toán tử AND & để xóa một bit ở vị trí n trong một số num:

num = num & ~(1 << n);
java

Ở đây 1 << n dịch chuyển 1 theo n bit sang trái, tạo ra một số có một bit duy nhất được đặt ở vị trí n. Sau đó, bằng cách sử dụng toán tử NOT ~, chúng ta lật tất cả các bit của số này, để số được tạo bây giờ có tất cả các bit được đặt thành 1 ngoại trừ bit thứ n là 0. Bằng cách sử dụng phép toán AND &, nó sẽ xóa bit ở vị trí n trong số bằng cách biến nó thành 0.

1 << 3 == 0b1000;
~(1 << 3) == 0b0111;

Ví dụ chi tiết

package leetcode;
import org.junit.jupiter.api.Test;
public class BitManipulation {
  public int clearBit(int num, int bitToClear) {
    return num & ~(1 << bitToClear);
  }

  @Test void testClearBit() {
    int num = 0b101001;
    int result = clearBit(num, 3);  //Xoá bit thứ 3
    System.out.println(Integer.toBinaryString(result));  //100001
  }
}
java

Lật một bit ở vị trí cụ thể (Bit Toggling)

Sử dụng toán tử XOR ^ để lật một bit tại một vị trí cụ thể trong một số nguyên.

public int flipBit(int num, int position) {
    int mask = 1 << position;
    return num ^ mask;
}
int num = 5;  // binary: 101
int flippedNum = flipBit(num, 2); // binary: 001
java

Lật tất cả các bit

Sử dụng toán tử NOT ~ để lật tất cả các bit của một số. Biểu thức ~num sẽ lật tất cả các bit của số, thay đổi 1 thành 00 thành 1.

int num = 5; // binary: 101
int result = ~num;
System.out.println(result);
java

Điều này sẽ xuất ra -6 dưới dạng nhị phân của -6 là 11111111111111111111111111111010, đây là phiên bản đảo ngược của 5.

Điều quan trọng cần lưu ý là toán tử NOT theo bit chỉ hoạt động trên các bit riêng lẻ của một số, nó không thay đổi dấu của số đó. Kết quả của phép toán là một số nguyên, vì vậy bit quan trọng nhất (bit dấu) trong kết quả sẽ giống với số ban đầu.

Bạn cũng có thể sử dụng thao tác XOR từng bit với -1 để lật tất cả các bit của một số.

int num = 5;
int result = num ^ -1;
System.out.println(result);
java

Đếm số bit 1 (Count bit 1)

Trong Java, bạn có thể sử dụng một vòng lặp và toán tử AND & để đếm số bit 1 trong một số.

Một cách để thực hiện việc này là sử dụng vòng lặp while để kiểm tra liên tục bit ngoài cùng bên phải của số và tăng số đếm nếu là bit 1.

int num = 11; // binary: 1011
int count = 0;
while (num != 0) {
    if ((num & 1) == 1) {
        count++;
    }
    num = num >> 1;
}
System.out.println("Number of bits set to 1 in " + num + " : " + count);
java

Chú ý: cách này chỉ áp dụng cho số dương, không đúng với số âm

Hàm đếm bit tổng quát với số int độ dài 32 bit như sau:

public int countBit(int num) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
      if ((num & 1) == 1) {
        count++;
      }
      num = num >> 1;
    }
    return count;
}
java

Còn đây là hàm kiểm thử với trường hợp số âm

@Test
void testCountBit() {
    int num = -11;
    int count = countBit(num);
    String binaryStringOfNum = Integer.toBinaryString(num);
    int countChar1 = 0;
    for (int j = 0; j < binaryStringOfNum.length(); j++) {
      if (binaryStringOfNum.charAt(j) == '1') {
        countChar1++;
      }
    }
    assertThat(count).isEqualTo(countChar1);
}
java

Đếm số bit 0

Để đếm bit 0 chúng ta có thể đếm bit 1 rồi lấy tổng số bit thể hiện số integer trừ đi là được.

Xác định số bit thể hiện một số nguyên dương

public int sizeOfbit(int num) {
    return (int)( Math.log(num) / Math.log(2)) + 1;
}

@Test void testsizeOfbit() {
    int num = 0b101001;
    assertThat(sizeOfbit(num)).isEqualTo(6);
    num = 0b101;
    assertThat(sizeOfbit(num)).isEqualTo(3);
}
java