190. Reverse Bits

Problem

Bài toán yêu cầu đảo ngược thứ tự các bit của một số nguyên không dấu 32 bit. Cụ thể, bit ở vị trí thấp nhất sẽ chuyển lên vị trí cao nhất và ngược lại, lặp lại cho toàn bộ 32 bit

Approach

Khởi tạo một biến res = 0

Lặp lại 32 lần (ứng với 32 bit)

Ở mỗi bước:

Lấy bit thấp nhất của n bằng n & 1

Dịch trái bit này lên vị trí tương ứng ở phía bên kia dãy bit: 31 - i

Gán bit này vào res bằng phép OR

Dịch phải n một bit để chuẩn bị cho vòng lặp tiếp theo

Return res sau khi hoàn thành

→ Cách làm này tận dụng thao tác bitwise, không dùng thêm cấu trúc dữ liệu nào khác nên rất tối ưu về thời gian và bộ nhớ

Solution

typescripttypescript

1function reverseBits(n: number): number {
2	let res = 0;
3	for(let i = 0; i < 32; i++) {
4		res = res | (n & 1) << (31 - i);
5		n = n >>> 1;
6	}
7	return res >>> 0;
8};

💡

n & 1: Lấy bit cuối cùng của n.

(n & 1) << (31 - i): Đưa bit vừa lấy được lên vị trí ngược lại (ví dụ: bit đầu sẽ đưa lên vị trí 31, bit thứ 2 lên vị trí 30, ...).

res | ...: Gộp bit vừa tính vào kết quả hiện tại.

n >>> = 1 dịch phải n một bit (dùng >>> để dịch phải không dấu)

res >>> 0 đảm bảo trả về kiểu số nguyên không đấu 32 bit

Lần lặp (i)	n (ban đầu)	n & 1	Dịch trái (<<)	res sau khi OR	n sau khi dịch phải
0	00000101	1	10000000	10000000	00000010
1	00000010	0	00000000	10000000	00000001
2	00000001	1	00100000	10100000	00000000
3 - 7	00000000	0	00000000	10100000	00000000

💡

res >>> 0?

Toán tử >>> là dịch phải không dấu (unsigned right shift) trong JavaScript/TypeScript.

Khi bạn dùng res >>> 0, nó sẽ chuyển giá trị của res thành số nguyên không dấu 32-bit.

Điều này đảm bảo rằng kết quả trả về luôn là một số nguyên không dấu (unsigned integer), ngay cả khi bit cao nhất (bit số 31) của res là 1 (tức là số âm nếu coi là signed integer).

Example 1: Số dương nhỏ

typescripttypescript

1let res = 5;
2console.log(res >>> 0); // Kết quả: 5

Example 2: Số âm (bit cao nhất là 1)

typescripttypescript

1let res = -3;
2console.log(res);        // Kết quả: -3
3console.log(res >>> 0);  // Kết quả: 4294967293

Giải thích:

Số -3 ở dạng nhị phân 32-bit: 11111111 11111111 11111111 11111101

Khi dùng >>> 0, JavaScript coi giá trị này là số không dấu, nên nó trở thành 4294967293.

typescripttypescript

1let x = -3;
2console.log(x.toString(2));       // "11111111111111111111111111111101"
3console.log((x >>> 0).toString(2)); // "11111111111111111111111111111101"

Kết quả nhị phân giống hệt nhau.

Khác biệt chỉ là khi đọc giá trị:

Nếu là signed: -3

Nếu là unsigned: 4294967293

Loading content...