190. Reverse Bits
Tags:
Easy
Skills:
Bitwise
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
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
res = 0n bằng n & 131 - ires bằng phép ORn một bit để chuẩn bị cho vòng lặp tiếp theores 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
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.| 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 |
>>> là dịch phải không dấu (unsigned right shift) trong JavaScript/TypeScript.res >>> 0, nó sẽ chuyển giá trị của res thành số nguyên không dấu 32-bit.res là 1 (tức là số âm nếu coi là signed integer).Example 1: Số dương nhỏ
1let res = 5;
2console.log(res >>> 0); // Kết quả: 5Example 2: Số âm (bit cao nhất là 1)
1let res = -3;
2console.log(res); // Kết quả: -3
3console.log(res >>> 0); // Kết quả: 4294967293Giải thích:
11111111 11111111 11111111 11111101>>> 0, JavaScript coi giá trị này là số không dấu, nên nó trở thành 4294967293.1let x = -3;
2console.log(x.toString(2)); // "11111111111111111111111111111101"
3console.log((x >>> 0).toString(2)); // "11111111111111111111111111111101"