Bit twiddling (part 3)
C
27
White

Hoàng Minh Trung viết ngày 26/09/2015

Câu đố:

Các bạn có biết đoạn code sau dùng để làm gì?

n & (n-1) == 0

Hãy thử không nhìn giải đáp ở dưới và suy nghĩ trong vòng vài phút xem sao :smile:

Giải đáp

Đoạn code trên check một điều kiện là n & (n-1) có bằng 0 hay không, tức là lời giải sẽ là kiểu nếu n có một đặc tính gì đó thì sẽ thoả mãn công thức trên đúng không :P.

Hãy thử một vài ví dụ nhé

Input: 111
Output: 111 & 110 == 110 

Input: 1001
Output: 1001 & 1000 == 1000

Ủa theo như trên thì n & (n-1) có vẻ sẽ là n-1 đúng không nhở, vậy thì đáp án sẽ là n & (n-1) == 0 tức là n-1 == 0 hay là n = 1!
Kết luận sớm quá vậy :P, từ ví dụ trên chúng ta có thể thấy nếu n có bit cuối cùng là 1 thì suy luận trên sẽ đúng, thử với trường hợp n có bit cuối là 0 xem sao.

Input: 110
Output: 110 & 101 == 100

Input 1100
Ouput: 1100 & 1011 == 1000

Input: 100 
Output: 100 & 011 = 0!!!!

Chúng ta observe một điều thú vị là, nếu n và n-1 có cùng số bit, thì kết quả sẽ luôn khác 0 bởi vì 1xxxx & 1yyyy sẽ luôn có kết quả là 1zzzz đúng không. Suy ra 2 đặc tính của n là:

  • Bit cuối là 0
  • n-1 sẽ giảm số bít đi

Từ 2 đặc tính trên chúng ta có thể "đoán" được là n chỉ có thể là dạng 1000..00
tức là n chính là số mũ của 2! Yay!

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Hoàng Minh Trung

21 bài viết.
53 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
17 15
(Ảnh) Mục đích của bài viết là hướng dẫn cơ bản nhất cho những ai chưa biết về docker, môi trường thực hiện là mac OS. Chuẩn bị Cài đặt virtua...
Hoàng Minh Trung viết hơn 2 năm trước
17 15
White
16 1
Bài viết dịch từ http://arslan.io/tenusefultechniquesingo Sử dụng một GOPATH duy nhất Sử dụng đồng thời nhiều GOPATH sẽ không giúp cho hệ thống ...
Hoàng Minh Trung viết hơn 1 năm trước
16 1
White
13 0
Bài viết dịch từ https://github.com/luciotato/golangnotes/blob/master/OOP.md Mục đích bài viết Học golang dễ dàng hơn với những kiến thức bạn đ...
Hoàng Minh Trung viết hơn 1 năm trước
13 0
Bài viết liên quan
White
3 1
Chú ý: Bài viết này trình bày chủ yếu cho CentOS 64 bit, tuy nhiên ý tưởng có thể áp dụng cho các hệ điều hành khác. Cuối bài có ghi chú cho Ubunt...
Ngoc Dao viết gần 2 năm trước
3 1
White
17 2
Gần đây tôi có dịp đụng vào CMake, nên có tìm hiểu một chút về nó. Hy vọng có ích cho anh em. Nó cung cấp tính năng sinh ra Makefile một cách hiệu...
Phùng Văn Tú viết hơn 2 năm trước
17 2
White
6 0
Xử lí song song từ xa xưa cho đến gần đây là lãnh vực cao cấp hầu như chỉ dành cho các nhà khoa học. Có ít nhất 2 nguyên nhân: Xử lí song song đòi...
Ngoc Dao viết gần 2 năm trước
6 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
21 bài viết.
53 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!