Bit twiddling (part 1)
C
29
White

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

Vừa đọc được một đoạn code khá thú vị trong source code của hadoop.
Đoạn code này nằm trong implementation của hdfs, được viết bằng C:

static uint32_t some_function_name(uint32_t i)
{
    if (i == 0) {
        return 1;
    }
    i--;
    i |= i >> 1;
    i |= i >> 2;
    i |= i >> 4;
    i |= i >> 8;
    i |= i >> 16;
    i++;
    return i;
}

Bạn có biết đoạn code trên dùng để làm gì?
Thôi không úp mở nữa tớ nói luôn, tên của hàm là round_up_to_power_of_2, tức là làm tròn i đến số gần nhất mà là số mũ của 2.

Một số ví dụ

input : 3, output : 4
input : 5, output : 8

Tại sao lại cần làm vậy thì trong rất nhiều logic bạn sẽ cần allocate một vùng nhớ là số mũ của 2 chẳng hạn, mà điển hình là trong xử lý ảnh, và như trong ví dụ ở trên, là ở hdfs khi mà cần allocate một block với độ lớn là số mũ của 2.

Tại sao đoạn code trên lại làm được việc đó, thì concept khá là thú vị, giả sử i có số bit có ý nghĩa là N (giả sử 5 là 101 thì N bằng 3), thì để tìm được 8, chúng ta sẽ làm thế nào để có N bit 1, sau đó bằng việc + thêm 1, thì chúng ta sẽ có N+1 bit bắt đầu bằng 1, còn lại là 0.

Giả sử với đầu vào là 221:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1101 | 0110 1110 = 1111 1111
n |= n >> 2;   // ...
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

Tại sao lại cần trừ đi 1 trước, thì là để trong trường hợp nếu đầu vào đã là số mũ của 2 sắn rồi.

Lưu ý là việc kết thúc ở 16 chứng tỏ thuật toán chỉ dành cho số nguyên 32 bit.

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

23 bài viết.
65 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
22 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 2 năm trước
22 1
White
19 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 3 năm trước
19 15
White
17 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 2 năm trước
17 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 hơn 2 năm trước
3 1
White
19 5
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 3 năm trước
19 5
White
8 1
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 hơn 2 năm trước
8 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
23 bài viết.
65 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á!