Một vài hàm builtin hữu dụng trong GCC Compiler

Bài viết này sẽ tập trung vào một số hàm built-in hữu ích và được sử dụng phổ biến trong lập trình thi đấu. Các hàm built-in là các hàm được cung cấp sẵn bởi trình biên dịch GCC giúp tăng hiệu suất và tiện lợi trong quá trình code, đặc biệt là những bài cần xử lí bit (bit manipulation).

__builtin_popcount

Hàm này trả về số bit được bật trong một kiểu số nguyên (int/long/long long)

Code

int x = 12;
cout << __builtin_popcount(x) << endl;
// 2

Lưu ý: Nếu \(x\) mang kiểu dữ liệu long, ta sẽ sử dụng __builtin_popcountl(x). Nếu \(x\) mang kiểu dữ liệu long long, ta sẽ sử dụng __builtin_popcountll(x).

long x = 10000000002;
cout << __builtin_popcountl(x) << endl;
// 12

long long  = 1000000000000000000;
cout << __builtin_popcountll(y) << endl;
// 24

Hàm này rất hay được sử dụng trong các bài tập liên quan đến bao hàm loại trừ, DP Bitmask, …

__builtin_parity

Hàm này trả về true nếu số bit được bật là lẻ, false nếu số bit được bật là chẵn

Code

int x = 12;
cout << __builtin_parity(x) << endl;
// 0
x = 13;
cout << __builtin_parity(x) << endl;
// 1

Lưu ý: Nếu \(x\) mang kiểu dữ liệu long, ta sẽ sử dụng __builtin_parityl(x). Nếu \(x\) mang kiểu dữ liệu long long, ta sẽ sử dụng __builtin_parityll(x).

long x = 10000000002;
cout << __builtin_parityl(x) << endl;
// 0

long long y = 1000000000000000000;
cout << __builtin_parityll(y) << endl;
// 0

Hàm này cũng được sử dụng phổ biến trong các bài tập về bao hàm loại trừ, DP Bitmask, …

__builtin_clz

Hàm này trả về số lượng bit 0 đứng ở đầu.

int x = 12; // 00000000 00000000 00000000 00001100
cout << __builtin_clz(x) << endl;
// 28

Nếu \(x\) mang kiểu dữ liệu long, ta sử dụng builtin_clzl(x), và với long long thì sử dụng builtin_clzll(x).

long long y = 1000000000000000000; 
// 00001101 11100000 10110110 10110011 
// 10100111 01100100 00000000 00000000
cout << __builtin_clzll(y) << endl;
// 4

Hàm này có thể được sử dụng trong việc tìm most significant bit (bit được bật đầu tiên từ bên trái sang).

int x = 12; // 000011000
cout << 31 - __builtin_clz(x) << endl;
// 3

__builtin_ctz

Hàm này trả về số lượng bit 0 đứng ở cuối

int x = 12; // 00000000 00000000 00000000 00001100
cout << __builtin_ctz(x) << endl;
// 2

Lưu ý: Nếu \(x\) mang kiểu dữ liệu long, ta sẽ sử dụng __builtin_ctzl(x). Nếu \(x\) mang kiểu dữ liệu long long, ta sẽ sử dụng __builtin_ctzll(x).

long long y = 1000000000000000000; 
// 00001101 11100000 10110110 10110011 
// 10100111 01100100 00000000 00000000
cout << __builtin_ctzll(y) << endl;
// 18

Hàm này có thể được sử dụng trong việc tìm least significant bit (bit được bật đầu tiên từ bên phải sang).

__builtin_ffs

Hàm này trả về bit được bật đầu tiên từ bên phải sang (index-1)

int x = 12; // 00000000 00000000 00000000 00001100
cout << __builtin_ffs(x) << endl;
// 3

Lưu ý: Nếu \(x\) mang kiểu dữ liệu long, ta sẽ sử dụng __builtin_ffsl(x). Nếu \(x\) mang kiểu dữ liệu long long, ta sẽ sử dụng __builtin_ffsll(x).

long long y = 1000000000000000000; 
// 00001101 11100000 10110110 10110011 
// 10100111 01100100 00000000 00000000
cout << __builtin_ffsll(y) << endl;
// 19

Lời kết

Phía trên là một vài hàm built-in trong GCC Compiler mà mình cảm thấy hữu ích để giúp việc giải bài trở nên nhanh gọn hơn. Lưu ý là các hàm trên chỉ tồn tại trong GCC Compiler, nếu các bạn dùng loại compiler khác thì sẽ không có các hàm built-in này.
Hi vọng các bạn thấy bài viết này hay, hữu ích và có thể áp dụng được trong các bài tập CP của chính mình!

Xem thêm tại: https://www.facebook.com/codedreamedu và https://codedream.edu.vn/hoc-thuat-toan/