Skip to content
TungDaDev's Blog

Bitwise trong Java: two's complement, mẹo lật bit và bitmask

Bitwise.webp
Published on
20 mins read

Có người viết n >> 1 thay cho n / 2 cho "nhanh". Test với số dương thì xanh hết. Rồi một hôm n là -7: -7 / 2 ra -3, còn -7 >> 1 lại ra -4.

Hai phép đó chỉ trùng nhau khi số không âm. Muốn biết vì sao thì phải nhìn xuống tận từng bit, và cũng nên biết khi nào bitwise đáng dùng, khi nào chỉ làm code khó đọc hơn.

# tại sao developer cần biết bitwise?

Mở source code của java.util.HashMap ra xem, chưa đọc được bao lâu bạn đã gặp biểu thức (h = key.hashCode()) ^ (h >>> 16) hay phép tính vị trí ô nhớ (n - 1) & hash. Phần lớn thời gian viết CRUD, gọi API hay làm validation hàng ngày, mình chẳng mấy khi đụng tới các phép toán trên bit. Nhưng hễ bước sang những bài toán cần gom gọn trạng thái hoặc tối ưu sát phần cứng, bitwise gần như là lựa chọn số một.

Gần gũi nhất với anh em làm Java enterprise là hệ thống phân quyền và feature flag. Thay vì tạo 32 cột boolean trong bảng database, người ta gom cả 32 quyền vào đúng một số int, giống hệt quyền file rwx = 111 = 7 trên Linux hay cách ghép cờ Pattern.CASE_INSENSITIVE | Pattern.MULTILINE trong JDK. Xuống sâu hơn ở tầng hạ tầng, bạn gặp bitwise khi parse protocol mạng dạng nhị phân, tính subnet mask, tách kênh màu ARGB, viết hàm băm (hashCode), hoặc trong ruột các cấu trúc dữ liệu như EnumSet, BitSet, ConcurrentHashMap. Và tất nhiên, đây cũng là dạng câu hỏi quen mặt trong các buổi phỏng vấn thuật toán.

# cơ bản: biểu diễn nhị phân

Trong máy tính, mọi con số suy cho cùng đều nằm dưới dạng một chuỗi bit 0 và 1. Trong Java, kiểu int chiếm cố định 32 bit và long chiếm 64 bit.

int a = 13;
// Binary: 0000 0000 0000 0000 0000 0000 0000 1101
//         = 8 + 4 + 1 = 13
 
int b = 7;
// Binary: 0000 0000 0000 0000 0000 0000 0000 0111
//         = 4 + 2 + 1 = 7
 
// Xem binary representation
System.out.println(Integer.toBinaryString(13));  // "1101"
System.out.println(Integer.toBinaryString(7));   // "111"
System.out.println(Integer.toBinaryString(-1));  // "11111111111111111111111111111111" (32 ones)
 
// Parse binary string thành int
int x = Integer.parseInt("1101", 2);  // 13
int y = 0b1101;  // Java literal binary (từ Java 7)

# số âm: two's complement

Java biểu diễn số nguyên có dấu bằng cơ chế Two's Complement (bù 2). Bit ngoài cùng bên trái (MSB - Most Significant Bit) đóng vai trò bit dấu: 0 là số không âm và 1 là số âm. Lý do phần cứng máy tính chọn bù 2 thay vì chỉ đổi mỗi bit đầu tiên (sign-magnitude) là để mạch điện CPU dùng chung một bộ cộng cho cả phép cộng lẫn phép trừ (a - b đơn giản là a + (-b)), đồng thời không bị lãng phí một trạng thái cho số -0.

Để tìm dạng bù 2 của một số âm -n, máy tính lật ngược toàn bộ các bit của n (~n) rồi cộng thêm 1:

// +5:  0000...0101
// -5:  1111...1011 (flip all bits of 5, then add 1)
 
int positive = 5;   // 0000 0000 0000 0000 0000 0000 0000 0101
int negative = -5;  // 1111 1111 1111 1111 1111 1111 1111 1011
 
// Verify: ~5 + 1 = -5
System.out.println(~5 + 1);  // -5

# các toán tử bitwise

# AND (&): cả hai bit đều 1 thì ra 1

Dùng để tắt bit (mask off) và kiểm tra một bit có đang bật không.

//   1101 (13)
// & 0111 (7)
// = 0101 (5)
 
int result = 13 & 7;  // 5
 
// Use case: Kiểm tra số chẵn/lẻ
boolean isOdd = (n & 1) == 1;   // Bit cuối cùng = 1 → lẻ
boolean isEven = (n & 1) == 0;  // Bit cuối cùng = 0 → chẵn
 
// Use case: Mask off upper bits (lấy lower 8 bits)
int lowerByte = value & 0xFF;  // 0xFF = 0000...11111111

# OR (|): chỉ cần một bit là 1 thì ra 1

Dùng để bật bit (set flag) và gộp nhiều option lại.

//   1101 (13)
// | 0111 (7)
// = 1111 (15)
 
int result = 13 | 7;  // 15
 
// Use case: Set a flag
int permissions = 0;
permissions |= READ;    // Bật READ flag
permissions |= WRITE;   // Bật WRITE flag (giữ READ)
 
// Use case: Combine regex flags
Pattern pattern = Pattern.compile("hello",
   Pattern.CASE_INSENSITIVE | Pattern.MULTILINE | Pattern.DOTALL);
// Internally: 2 | 8 | 32 = 42 = 101010 in binary

# XOR (^): khác nhau ra 1, giống nhau ra 0

Dùng để đảo bit (toggle), swap hai số, tìm phần tử không bị lặp.

//   1101 (13)
// ^ 0111 (7)
// = 1010 (10)
 
int result = 13 ^ 7;  // 10
 
// Use case: Toggle a flag
flags ^= DARK_MODE;  // Bật nếu đang tắt, tắt nếu đang bật
 
// Use case: Swap 2 số KHÔNG dùng temp variable
a ^= b;  // a = a XOR b
b ^= a;  // b = b XOR (a XOR b) = original a
a ^= b;  // a = (a XOR b) XOR a = original b
// Mẹo này chủ yếu để đi phỏng vấn: không nhanh hơn dùng biến tạm,
// và hỏng nếu a, b cùng trỏ một chỗ (vd arr[i] ^= arr[j] với i == j → về 0)
 
// Use case: Tìm số xuất hiện 1 lần (mọi số khác xuất hiện 2 lần)
int[] nums = {2, 3, 5, 3, 2};
int unique = 0;
for (int num : nums) unique ^= num;
// 0^2^3^5^3^2 = 5 (pairs cancel out: x^x=0)
 
// XOR properties:
// a ^ 0 = a        (identity)
// a ^ a = 0        (self-inverse)
// a ^ b = b ^ a    (commutative)
// (a ^ b) ^ c = a ^ (b ^ c)  (associative)

# NOT (~): lật hết các bit

// ~13 = ~(0000...1101) = 1111...0010 = -14 (two's complement)
int result = ~13;  // -14
 
// Relationship: ~n = -(n+1)
// ~0 = -1, ~1 = -2, ~(-1) = 0
 
// Use case: Tạo bitmask "tất cả trừ bit X"
int allExceptBit3 = ~(1 << 3);  // 1111...11110111
permissions &= allExceptBit3;    // Clear bit 3

# left shift (<<): dịch trái, thêm 0 bên phải

Dịch trái 1 bit là nhân 2. Dịch trái n bit là nhân 2^n.

// 13 << 2 = 1101 << 2 = 110100 = 52
int result = 13 << 2;  // 13 * 4 = 52
 
// Use case: Nhân nhanh với power of 2
int doubled = n << 1;      // n * 2
int quadrupled = n << 2;   // n * 4
int times8 = n << 3;       // n * 8
 
// Use case: Tạo bitmask cho position cụ thể
int bit0 = 1 << 0;  // 0001 = 1
int bit1 = 1 << 1;  // 0010 = 2
int bit2 = 1 << 2;  // 0100 = 4
int bit3 = 1 << 3;  // 1000 = 8

# right shift (>>): dịch phải, giữ bit dấu (arithmetic shift)

Dịch phải 1 bit là chia 2 (làm tròn xuống). Bit dấu được chép sang các ô trống bên trái (sign extension).

// 13 >> 2 = 1101 >> 2 = 0011 = 3
int result = 13 >> 2;  // 13 / 4 = 3 (truncated)
 
// Negative: -8 >> 1 = -4 (sign bit preserved)
int neg = -8 >> 1;  // -4
 
// Use case: Chia nhanh power of 2 (chỉ đúng với n >= 0)
int half = n >> 1;      // n / 2
int quarter = n >> 2;   // n / 4
// Với số âm thì khác: -7 >> 1 = -4 (làm tròn xuống), còn -7 / 2 = -3 (cắt phần lẻ về 0)
 
// Use case: Mid point (avoid overflow)
int mid = (low + high) >>> 1;  // Safer than (low + high) / 2

# unsigned right shift (>>>): dịch phải, thêm 0 bên trái (bỏ qua dấu)

// -1 >>> 1 = 0111...1111 = Integer.MAX_VALUE = 2147483647
int result = -1 >>> 1;  // 2147483647
 
// Difference: >> vs >>>
// -8 >> 1  = -4   (sign extended: 1111...1000 >> 1 = 1111...1100)
// -8 >>> 1 = 2147483644 (zero filled: 1111...1000 >>> 1 = 0111...1100)
 
// Use case: Unsigned division by power of 2
// Use case: Hash code distribution (HashMap internal)
static int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   // XOR upper 16 bits with lower 16 bits → better distribution
}

# common bit manipulation tricks

# check, set, clear, toggle specific bit

// Position = 0-indexed from right (LSB = position 0)
 
// CHECK if bit N is set
boolean isSet = (value & (1 << n)) != 0;
 
// SET bit N (turn on)
value |= (1 << n);
 
// CLEAR bit N (turn off)
value &= ~(1 << n);
 
// TOGGLE bit N (flip)
value ^= (1 << n);
 
// Example:
int flags = 0b1010;  // bits 1 and 3 are set
boolean bit2Set = (flags & (1 << 2)) != 0;  // false (bit 2 is 0)
flags |= (1 << 2);   // flags = 0b1110 (set bit 2)
flags &= ~(1 << 1);  // flags = 0b1100 (clear bit 1)
flags ^= (1 << 3);   // flags = 0b0100 (toggle bit 3 off)

# power of 2 check

Một số nguyên dương là lũy thừa của 2 (1, 2, 4, 8, 16...) khi và chỉ khi dạng nhị phân của nó có đúng một bit 1 duy nhất. Khi lấy n - 1, bit 1 đó sẽ lật về 0 và toàn bộ các bit 0 phía sau nó lật hết thành 1, nên phép n & (n - 1) chắc chắn ra 0:

// n là power of 2 khi chỉ có đúng 1 bit = 1
// 8 = 1000, 8-1 = 0111 → 1000 & 0111 = 0000 → is power of 2
boolean isPowerOf2 = n > 0 && (n & (n - 1)) == 0;
 
// 6 = 0110, 6-1 = 0101 → 0110 & 0101 = 0100 ≠ 0 → NOT power of 2

# count set bits (population count)

Cũng nhờ tính chất n & (n - 1) luôn xoá đi bit 1 nằm thấp nhất bên phải (thuật toán Brian Kernighan), ta có thể đếm số bit 1 với số vòng lặp đúng bằng số bit đang bật thay vì phải duyệt đủ 32 lần. Tất nhiên trên thực tế, hãy gọi hàm có sẵn Integer.bitCount(n) vì JVM sẽ dịch thẳng nó thành một lệnh phần cứng POPCNT trên CPU hiện đại:

// Built-in (fastest — uses CPU instruction on modern hardware)
int count = Integer.bitCount(n);
 
// Manual (Brian Kernighan's algorithm)
int count = 0;
while (n != 0) {
   n &= (n - 1);  // Clear lowest set bit
   count++;
}
// n = 1011 → 1010 → 1000 → 0000 (3 iterations = 3 set bits)

# lowest/highest set bit

Ngược với việc xoá bit 1 thấp nhất, nếu muốn giữ lại đúng một mình bit 1 thấp nhất đó và tắt hết các bit còn lại, ta dùng n & (-n) (nhờ tính chất bù 2, -n tức ~n + 1 sẽ đảo ngược toàn bộ phần bit phía trước bit 1 thấp nhất và giữ nguyên từ bit đó trở về sau):

// Lowest set bit (rightmost 1)
int lowest = n & (-n);  // Isolate lowest set bit
// 12 = 1100, -12 = 0100 (two's complement), 1100 & 0100 = 0100 = 4
 
// Position of lowest set bit
int pos = Integer.numberOfTrailingZeros(n);  // 12 → 2
 
// Highest set bit position
int pos = 31 - Integer.numberOfLeadingZeros(n);  // 12 → 3
// Hoặc: Integer.highestOneBit(12) = 8 (bit value, not position)

# real-world use cases trong java

# use case 1: permission bitmask system

Khi thiết kế bảng phân quyền đơn giản, thay vì tạo hàng chục cột boolean hay join bảng phụ cho mỗi lần kiểm tra request, bạn có thể gán mỗi quyền vào một vị trí bit (1 << 0, 1 << 1, 1 << 2...) và lưu tổng quyền của user vào đúng một cột INTEGER:

public class Permission {
   public static final int NONE    = 0;         // 0000 0000
   public static final int READ    = 1 << 0;    // 0000 0001 = 1
   public static final int WRITE   = 1 << 1;    // 0000 0010 = 2
   public static final int DELETE  = 1 << 2;    // 0000 0100 = 4
   public static final int ADMIN   = 1 << 3;    // 0000 1000 = 8
   public static final int EXPORT  = 1 << 4;    // 0001 0000 = 16
   public static final int IMPORT  = 1 << 5;    // 0010 0000 = 32
 
   // Common combinations
   public static final int EDITOR = READ | WRITE;            // 3
   public static final int MANAGER = READ | WRITE | DELETE;  // 7
   public static final int FULL = READ | WRITE | DELETE | ADMIN | EXPORT | IMPORT;  // 63
 
   private int userPermissions;
 
   public Permission(int permissions) {
       this.userPermissions = permissions;
   }
 
   // Check permission
   public boolean hasPermission(int permission) {
       return (userPermissions & permission) == permission;
   }
 
   // Check ANY of given permissions
   public boolean hasAny(int permissions) {
       return (userPermissions & permissions) != 0;
   }
 
   // Grant permission
   public void grant(int permission) {
       userPermissions |= permission;
   }
 
   // Revoke permission
   public void revoke(int permission) {
       userPermissions &= ~permission;
   }
 
   // Toggle permission
   public void toggle(int permission) {
       userPermissions ^= permission;
   }
}
 
// Usage:
Permission user = new Permission(Permission.READ | Permission.WRITE);
user.hasPermission(Permission.READ);    // true
user.hasPermission(Permission.DELETE);   // false
user.hasPermission(Permission.EDITOR);  // true (has both READ and WRITE)
user.grant(Permission.DELETE);           // Now has READ | WRITE | DELETE
user.revoke(Permission.WRITE);          // Now has READ | DELETE
 
// Store in database as single integer column:
// user_permissions INTEGER DEFAULT 0
// Rất compact: 1 int lưu được 32 permissions thay vì 32 boolean columns

# use case 2: enumset, bitmask có sẵn của java cho enum

Tự viết class Permission với hằng số int như trên giúp hiểu rõ cơ chế, nhưng trong dự án Java thực tế bạn nên ưu tiên EnumSet. Bên dưới, khi enum của bạn có từ 64 phần tử trở xuống, Java dùng class RegularEnumSet gói gọn toàn bộ tập hợp vào duy nhất một biến long 64-bit (nếu trên 64 phần tử thì tự động chuyển sang JumboEnumSet dùng mảng long[]). Bạn vừa có được tốc độ O(1) của phép toán bit, vừa giữ được type-safety của Enum:

public enum Feature {
   DARK_MODE,      // ordinal 0 → bit 0
   NOTIFICATIONS,  // ordinal 1 → bit 1
   ANALYTICS,      // ordinal 2 → bit 2
   BETA_FEATURES,  // ordinal 3 → bit 3
   TWO_FACTOR_AUTH // ordinal 4 → bit 4
}
// EnumSet internally uses bitmask (long for ≤64 enums)
EnumSet<Feature> userFeatures = EnumSet.of(Feature.DARK_MODE, Feature.ANALYTICS);
// Internal: 00101 (bits 0 and 2 set)
 
userFeatures.add(Feature.NOTIFICATIONS);     // Internal: 00111
userFeatures.contains(Feature.BETA_FEATURES); // false (bit 3 not set)
userFeatures.remove(Feature.DARK_MODE);       // Internal: 00110
 
// EnumSet operations = bitwise operations → O(1), extremely fast
EnumSet<Feature> all = EnumSet.allOf(Feature.class);     // 11111
EnumSet<Feature> none = EnumSet.noneOf(Feature.class);   // 00000
EnumSet<Feature> complement = EnumSet.complementOf(userFeatures); // flip all

# use case 3: bên trong hashmap, tính bucket index

// HashMap uses bitwise AND instead of modulo for bucket index
// Why? n & (capacity-1) is faster than n % capacity (when capacity is power of 2)
 
// HashMap.putVal() simplified:
int hash = hash(key);
int index = hash & (table.length - 1);  // Equivalent to hash % table.length (khi hash >= 0)
// But only works when table.length is power of 2 (which HashMap guarantees)
// Thêm một lợi ích: hash âm thì % ra số âm (-37 % 16 = -5), còn & luôn ra index hợp lệ (-37 & 15 = 11)
 
// Example: capacity = 16, hash = 37
// 37 % 16 = 5     (modulo — slow division)
// 37 & 15 = 5     (bitwise AND — fast, no division)
// 37 = 100101
// 15 = 001111
// &  = 000101 = 5 ✓
 
// This is why HashMap capacity is ALWAYS power of 2
// tableSizeFor(): rounds up to nearest power of 2
// (bản JDK 8; từ JDK 13 viết gọn hơn: int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);)
static final int tableSizeFor(int cap) {
   int n = cap - 1;
   n |= n >>> 1;
   n |= n >>> 2;
   n |= n >>> 4;
   n |= n >>> 8;
   n |= n >>> 16;
   return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

# use case 4: color manipulation (ARGB)

// Color stored as 1 int: AAAA AAAA RRRR RRRR GGGG GGGG BBBB BBBB
int color = 0xFF3366CC;  // Alpha=255, R=51, G=102, B=204
 
// Extract components
int alpha = (color >>> 24) & 0xFF;  // Shift right 24, mask lower 8 bits
int red   = (color >>> 16) & 0xFF;  // Shift right 16, mask lower 8 bits
int green = (color >>> 8) & 0xFF;   // Shift right 8, mask lower 8 bits
int blue  = color & 0xFF;           // Mask lower 8 bits
 
// Combine components back
int newColor = (alpha << 24) | (red << 16) | (green << 8) | blue;
 
// Darken color (multiply each channel by 0.7)
int darken(int color) {
   int a = (color >>> 24) & 0xFF;
   int r = (int)(((color >>> 16) & 0xFF) * 0.7);
   int g = (int)(((color >>> 8) & 0xFF) * 0.7);
   int b = (int)((color & 0xFF) * 0.7);
   return (a << 24) | (r << 16) | (g << 8) | b;
}

# use case 5: network, subnet mask

// IP Address: 192.168.1.100
// Subnet Mask: 255.255.255.0 (/24)
 
int ip = (192 << 24) | (168 << 16) | (1 << 8) | 100;
int mask = 0xFFFFFF00;  // 255.255.255.0 = /24
 
// Network address = IP AND mask
int network = ip & mask;  // 192.168.1.0
 
// Broadcast address = IP OR (~mask)
int broadcast = ip | ~mask;  // 192.168.1.255
 
// Check if 2 IPs are in same subnet
boolean sameSubnet = (ip1 & mask) == (ip2 & mask);
 
// Create mask from CIDR prefix length
int createMask(int prefixLength) {
   return prefixLength == 0 ? 0 : (0xFFFFFFFF << (32 - prefixLength));
}
// createMask(24) = 0xFFFFFF00 = 255.255.255.0
// createMask(16) = 0xFFFF0000 = 255.255.0.0

# bitwise vs arithmetic: chuyện performance

JVM với CPU bây giờ thường tự đổi phép số học sang bitwise khi tối ưu được. Vì vậy đừng hy sinh tính dễ đọc chỉ để tối ưu vặt. Có điều biết mấy cặp tương đương dưới đây thì đọc code người khác dễ hơn nhiều:

// Equivalent operations (compiler often optimizes automatically):
n * 2    ↔  n << 1
n * 4    ↔  n << 2
n * 8    ↔  n << 3
n / 2    ↔  n >> 1     (for positive n; signed shift)
n / 4    ↔  n >> 2
n % 2    ↔  n & 1      (for positive n)
n % 4    ↔  n & 3
n % 8    ↔  n & 7
n % 16   ↔  n & 15     (n % 2^k = n & (2^k - 1), khi n > 0)
 
// Khi readability quan trọng hơn → dùng arithmetic
// Khi performance critical (inner loop, millions iterations) → bitwise CÓ THỂ nhanh hơn
// Khi viết framework/library internals → bitwise acceptable (HashMap, ConcurrentHashMap)

# common interview problems

# problem: single number (leetcode 136)

Số nào cũng xuất hiện 2 lần, chỉ có 1 số xuất hiện 1 lần. Tìm số đó.

public int singleNumber(int[] nums) {
   int result = 0;
   for (int num : nums) {
       result ^= num;  // Pairs cancel: x^x=0, remains: 0^unique=unique
   }
   return result;
}
// O(n) time, O(1) space — không thể tốt hơn

# problem: counting bits (leetcode 338)

Cho n, trả về mảng với array[i] = số bit 1 của i (0 ≤ i ≤ n).

public int[] countBits(int n) {
   int[] dp = new int[n + 1];
   for (int i = 1; i <= n; i++) {
       dp[i] = dp[i >> 1] + (i & 1);
       // i>>1 bỏ bit cuối → đã tính trước
       // i&1 thêm bit cuối (0 hoặc 1)
   }
   return dp;
}
// O(n) time — mỗi element O(1)

# problem: reverse bits (leetcode 190)

public int reverseBits(int n) {
   int result = 0;
   for (int i = 0; i < 32; i++) {
       result = (result << 1) | (n & 1);  // Shift result left, add last bit of n
       n >>>= 1;                           // Shift n right (unsigned)
   }
   return result;
}

# tóm tắt

OperatorSymbolMnemonicCommon Use
AND&"Cả hai"Check/clear bits, mask
OR|"Ít nhất 1"Set bits, combine flags
XOR^"Khác nhau"Toggle, find unique, swap
NOT~"Đảo ngược"Invert mask
Left Shift<<"Nhân 2^n"Create bit positions, multiply
Right Shift>>"Chia 2^n (signed)"Divide, sign-preserving
Unsigned Right Shift>>>"Chia 2^n (unsigned)"Hash distribution, unsigned ops

Khi nào nên và không nên dùng bitwise trên production?

Bitwise đáng dùng khi làm permission/flag cần lưu gọn, xử lý tập enum qua EnumSet, parse gói tin mạng hay màu nhị phân, hoặc viết hàm băm và vòng lặp nóng cần vắt từng chu kỳ CPU.

Còn trong code nghiệp vụ hằng ngày thì đừng cố viết x << 1 thay cho x * 2, cũng đừng nhồi cờ vào một số nguyên khi chưa cần. JIT đã tự đổi nhân/chia cho lũy thừa của 2 sang shift rồi. Viết bằng phép số học dễ đọc hơn, và nếu team không quen bitwise thì chi phí bảo trì lớn hơn cái lợi về tốc độ.

Quy tắc mình thấy dễ nhớ: chỗ nào trong code nghiệp vụ có >>, >>> hay & với một hằng số lạ, chỗ đó phải có test chạy cả số âm, và nếu đó là tập enum thì thử thay bằng EnumSet trước đã.

Chỉ là những ghi chép cá nhân với hy vọng mang lại chút giá trị. Nếu thấy hữu ích, đừng ngại chia sẻ cho bạn bè & đồng nghiệp nhé!

Happy coding 😎 👍🏻 🚀 🔥.