Bitwise và ứng dụng

Bitwise là gì?

Trong khoa học máy tính thì đó là các thao tác trên 1 hoặc nhiều chuỗi nhị phân. Thông thường các phép tính bitwise nhanh hơn rất nhiều so với phép nhân, phép chia, đôi khi nhanh hơn đáng kể so với phép cộng. Tuy nhiên thì mặt trái của nó là khó đọc và debug thì rất khổ.

Các phép toán cơ bản:

Operator	Name	Description
&	AND	Nếu cả 2 bit là 1, giá trị trả về là 1, ngược lại trả về 0.
\|	OR	Nếu một trong hai bit là 1, giá trị trả về là 1, ngược lại trả về 0.
^	XOR	Nếu hai bit khác nhau, giá trị trả về là 1, ngược lại trả về 0.
~	NOT	Đảo ngược tất cả các bit, 0 thành 1 và 1 thành 0.
<<	Zero fill left shift	Dịch chuyển tất cả các bit sang bên trái.
>>	Signed right shift	Dịch chuyển tất cả các bit sang bên phải bit được fill vào phụ thuộc vào bit dấu (sign-extension)
>>>	Zero fill right shift	Dịch chuyển tất cả các bit sang bên phải và bit được fill vào luôn là 0 (zero-extension)

Ứng dụng và các trick với bitwise.

Compression, Encryption

Cả 2 lĩnh vực trên đều phụ thuộc vào các thuật toán sử dụng bitwise. Ví dụ http://www.solverworld.com/bitwise-compression-what-is-it/

https://en.wikipedia.org/wiki/XOR_cipher/

Bit fields (flags)

1 trong các ứng dụng của bit là thể hiện trạng thái bật tắt, hoặc đánh dấu sự tồn tại hoặc không. Trong Unity anh em chắc là biết layer mask

Kiểu dữ liệu này là LayerMask và nó chính là 1 int, có 32 bit, mỗi bit trong LayerMask tương đương 1 layer => trong game chúng ta có tối đa 32 layer khác nhau. Như hình trên thì giá trị 8 bit đầu của LayerMask là: 000110111 tương ứng với các layer Default, TransparentFX, ….

1 trong các ứng dụng phổ biến trong unity của nó là dùng để check raycast.

RaycastHit2D hit = Physics2D.Raycast(transform.position, travelDirection, 1.0f,layerMask);

1 ví dụ nữa của bit-flag trong phân quyền user:

[Flags]
public enum SecurityLevel
{
    User = 1, // 0001
    SuperUser = 2, // 0010
    QuestionAdmin = 4, // 0100
    AnswerAdmin = 8 // 1000
}

Set quyền cho user thành SuperUser và AnswerAdmin

// Set User Permissions to 1010
//
//   0010
// | 1000
//   ----
//   1010
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

Check permission của user trước khi cho phép thực hiện 1 action:

// Check if the user has the required permission group
//
//   1010
// & 1000
//   ----
//   1000
if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin )
{
    // Allowed
}

1 trick khá thú vị swap 2 số int

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B
 
A = 13 // 00001101
B = 25 // 00011001
 
//   00001101
// ^ 00011001
//   00010100
A = A^B 
 
//   00010100
// ^ 00011001
//   00001101
B = A^B // B = 13
 
//   00010100
// ^ 00001101
//   00011001
A = A^B //A = 25

Trong dự án HOE áp dụng khá nhiều các phép toán trên bit để xử lý làm nhỏ gói dữ liệu trong trận khi truyền từ server về client, vì sao phải làm nhỏ gói dữ liệu, lý do là game mobile nên cần tối ưu tối đa về lượng data trao đổi trong trận đấu, tiết kiệm chi phí vận hành.

Ví dụ data của 1 unit trong trận đấu có các trường sau:

class BaseGameEntity
{
   public int CardId;
   public byte TeamId;
   public Vector2 Position;
   ....
}

Nếu để nguyên data như này để gửi đi thì dung lượng của gói tin sẽ = 32 + 8 +32 + 32 = 104 bit, có vẻ không lớn lắm nhưng thử làm 1 phép tính, có trung bình 30 unit trên sân và trận đấu diễn ra trong 2p, mỗi giây data được gửi 5 lần thì tổng lượng data của trận đấu sẽ là: 104 * 30 * 5 * 60 * 2 = 1872000 bits = 0.223 Megabytes.

Như trường CardId thì giá trị của nó có range [0, 200], có nghĩa nó chỉ cần 8 bit là thừa đủ rồi chứ không cần đến tận 32bit của 1 int. Tương tự với teamId chỉ có 2 giá trị 0 và 1 thì chỉ cần 1 bit là đủ và Position là 10 bit với mỗi chiều, phần position này hơi phức tạp 1 chút sẽ giải thích dần ở đoạn tiếp theo… Vậy theo tính toán sơ bộ thì cả 3 trường trên chiếm 29 bit và có thể gộp data của 3 trường trên vào 1 biến int.

Chúng ta thử tính toán lại lượng data, thay số 104 ở trên bằng 32 => lượng data giảm đi 104/32 = 3.25 lần => 0.0686 Megabytes. Kỹ thuật được sử dụng ở trên được gọi là là Bit-packing. Nguyên lý của nó là loại bỏ phần data dư thừa, gộp data lại với nhau khít nhất có thể để giảm dung lượng gói tin.

VD:

Cách triển khai

Xác định số bit dành cho mỗi trường

//CardId = 54
//TeamId = 1
//Pos = (-2.2 ; 1.8)
 
//Xác định số bit tối đa cho mỗi trường dữ liệu
public static int numOfBitCardId = 7;
public static int numOfBitTeamId = 1;
public static int numOfBitPosition = 10;

Pack Data: nguyên lý phần này khá đơn giản, sử dụng phép dịch bit để ghép các phần data vào chung 1 chỗ

int data = 0;
data = data + cardId;       // 00110110
data = data<<numOfBitTeamId;// 01101100
data += TeamId              // 01101101

Như vậy đã ghép được phần cardId và teamId, còn Data của position có 2 phần x,y có kiểu dữ liệu float và giới hạn chiều x[-3.0; 3.0] và y[-4.7; 4.7], để ghép data của position vào chung thì cần xử lý thêm.
Đầu tiên là đưa dữ liệu x,y của position về số dương.

BattleConfigs.OFFSET_X = 3.0f;
BattleConfigs.OFFSET_Y = 4.7f;
 
x = pos.x + BattleConfigs.OFFSET_X
y = pos.y + BattleConfigs.OFFSET_Y

Tiếp theo là chuyển data của position về số nguyên, ở đây chúng ta có 10 bit cho x và 10 bit cho y, như vậy khoảng giá trị cho mỗi chiều là[0; 2^10 -1] = [0;1023]. Ý tưởng để xử lý là chúng ta chuyển từ hệ tọa độ số thực của game sang hệ tọa độ số nguyên mới với giá trị của 2 chiều x,y có range = [0; 1023].

....
int maskPos = (1 << numOfBitPosition) - 1; //1023
 
float OFFSET_X = 3.0f;
float OFFSET_Y = 4.7f;
 
flaot reverseWidth = 1/(2*OFFSET_X);
float reverseHeight = 1/(2*OFFSET_Y);
 
x = Mathf.RoundToInt((pos.x + OFFSET_X) * reverseWidth * maskPos);
y = Mathf.RoundToInt((pos.y + OFFSET_Y) * reverseHeight * maskPos);
 
//đề phòng giá trị vượt quá ngưỡng 1023
if (x > maskPos) x = maskPos;
if (y > maskPos) y = maskPos;
// ghép vào phần data chung
data = data << numOfBitPosition;
data += x;
data = data << numOfBitPosition;
data += y;

Đến đây cơ bản là xong phần pack data với nhau, tiếp theo là phần unpack. Với data được pack ở phần trên thì dữ liệu có thứ tự như sau:

theo chiều từ phải sang trái 10 bit đầu là giá trị y, 10 bit tiếp là giá trị của x, 1 bit tiếp là teamId và còn lại là CardId, để lấy được data từng phần ra ta sử dụng bitmask, phép toán AND và phép dịch bit phải >>.

int maskPos = (1 << numOfBitPosition) - 1; //1023
int maskTeamId = (1<< numOfBitTeamId) -1; //1
int scrData;
//lấy data position
//   00000110110110000101000100100001
// & 00000000000000000000001111111111
//   00000000000000000000000100100001
int y = scrData&maskPos;
// 00000110110110000101000100100001 >> 10
// 00000000000000011011011000010100
scrData = scrData >> numOfBitPosition;
 
//   000000011011011000010100
// & 000000000000001111111111
//   000000000000001000010100
int x = scrData & maskPos;
// 000000011011011000010100 >> 10
// 000000000000000001101101
scrData = scrData >> numOfBitPosition;
 
x = ((x / maskPos) /  reverseHeight ) - OFFSET_X;
y = ((y / maskPos) /  reverseHeight ) - OFFSET_Y;
Vector2 pos = new Vector2(x,y);
 
//   01101101
// & 00000001
//   00000001
int teamId = scrData & maskTeamId;
// 01101101 >> 1
// 00110110
scrData = scrData >> numOfBitTeamId;
 
// 00110110 = 54
int cardId = scrData;

Giá trị của scrData khi lấy được teamId xong bằng chính cardId luôn nên không cần phải thực hiện phép toán AND với mask của nó nữa.

Nhấn để đánh giá bài viết!

[Số đánh giá: 0 Trung bình: 0]

PROGRAMMING

Bitwise là gì?

Các phép toán cơ bản:

Ứng dụng và các trick với bitwise.

Compression, Encryption

Bit fields (flags)

Leopotam/ecs

TỐI ƯU AUDIO ASSET TRONG UNITY

Có thể bạn quan tâm

Để lại bình luận Hủy trả lời