Scribd
Unggah
9 tayangan15 halaman

Teknik Bitmask dalam Pemrograman

Dokumen ini membahas tentang bitmask, teknik manipulasi bit yang sering digunakan dalam pemrograman untuk menyelesaikan masalah dengan efisien. Bitmask dapat dikombinasikan dengan teknik lain seperti DP dan Segment Tree, serta memiliki berbagai operasi bitwise seperti shift, OR, AND, dan XOR. Selain itu, dokumen ini juga mencantumkan beberapa masalah yang dapat diselesaikan menggunakan teknik bitmask.

Diunggah oleh

dawnson.sng14
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd
9 tayangan15 halaman

Teknik Bitmask dalam Pemrograman

Dokumen ini membahas tentang bitmask, teknik manipulasi bit yang sering digunakan dalam pemrograman untuk menyelesaikan masalah dengan efisien. Bitmask dapat dikombinasikan dengan teknik lain seperti DP dan Segment Tree, serta memiliki berbagai operasi bitwise seperti shift, OR, AND, dan XOR. Selain itu, dokumen ini juga mencantumkan beberapa masalah yang dapat diselesaikan menggunakan teknik bitmask.

Diunggah oleh

dawnson.sng14
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd

Bitmask

Eryawan P
Bitmask??

Simply, work on bit-level


Solving problem by manipulating bit
Why?

● Banyak dikombinasikan dengan teknik lain ( DP, Segment Tree, Adhoc )


● Bruteforce garis keras kebanyakan memakai bitmask (N<=16)
● Mempersingkat code
● Memperkeren code
Operasi pada bit (Bitwise)
1. Shift Right (a >> x )

Semua bit representasi a digeser ke kanan sebanyak x kali, bit kanan dihapus dan bit kiri
diisi 0

Sama aja membagi dengan 2^x

floor(a/2) ⇐⇒ a >> 1

floor(a/(2^x)) ⇐⇒ a >> x
2. Shift Left ( a << x )

Semua bit representasi a digeser ke kiri sebanyak x kali, bit kiri dihapus dan bit kanan diisi
0

Sama aja mengali dengan 2^x

a*2 ⇐⇒ x << 1

a*(2^x) ⇐⇒ a << x
3. OR ( a | b )

● Untuk mengaktifkan bit pada sebuah posisi


4. AND ( a & b )

● Untuk mengecek apakah bit pada sebuah posisi hidup


5. XOR ( a ^ b )

● Untuk mematikan bit pada sebuah posisi


Teknik teknik
__builtin_popcount

Menghitung banyaknya bit yang nyala

Builtin function g++

Harus pake compiler g++

Hardware optimization, makanya lebih cepet dari implemen sendiri


XOR Properties

A^B=C

A^C=B

A1^A2^...^AN =K

K^A2^A3^...^AN = A1

A1^A3^...^AN ^K = A2
Another properties

a+b = (a xor b) + (a and b)*2


Problems

● Traveling Salesman Problem (Graph + Shortest path + DP)


● [Link] ( DP )
● [Link]
● [Link]
Ty ty

Anda mungkin juga menyukai