Dùng phép toán trên bít để giải các bài toán

[olat]

Đây là một số bài toán, Mình đã tìm ra một số giải thuật, các bạn hãy tham khảo và đưa ra những cách khác, mình muốn tìm những cách hay hơn:

1.
Viết chương trình cho nhập vào một số nguyên N. Dùng phép toán trên bít để:
a) Kiểm tra và in ra N là số chẵn hay lẻ ? (Một số nguyên là chẵn nếu bít đầu tiên của nó là 0).
b) Kiểm tra và in ra cho biết số N này có chia hết cho 8 hay không ?
c) Tìm số nguyên lớn nhất M chia hết cho 8 và M≤N.
d) Tìm số nguyên lớn nhất M chia hết cho 32 và M≤N.
e) Kiểm tra và in ra cho biết số N là âm hay không âm ? (Cho biết, bít cuối cùng của N là 1 nếu N là số âm)
2.
Viết chương trình cho nhập vào số nguyên N và số tự nhiên M.
a) Hãy in ra cho biết bít thứ M của N là “bật” (1) hay “tắt” (0) ?
b) Hãy bật bít thứ M của N.
c) Hãy đảo bít thứ M của N (bật thành tắt, và tắt thành bật).
1a.
Cách 1 : N&1
Nếu kết quả là 1 : N lẻ. Ngược lại, N chẵn.
vd : N=5 --->00000101
N&1 (00000001) --->00000001=1
Vậy N lẻ
Cách 2 : N<<(n-1)
Nếu Kq=0 : N chẵn. Ngược lại, N lẻ.
(n là số bít)
vd: N=5
dịch trái 7 bit : 10000000---> Khác 0
Vậy N lẻ.
1b.
N<<(n-3)
Nếu Kq=0 : N chia hết cho 8. Ngược lại, không chia hết cho 8.
Vd : N=16 ---> 00010000
N<<5 : 00000000=0
Vậy N chia hết cho 8
N=9 ---> 00001001
N<<5 : 00100000 <>0 ---> N không chia hết cho 8
1c.
Cách 1 : N>>3 (hủy 3 bit đầu)
N<<3 = M (lấy Kq bước 1 để làm tiếp bước 2)

Cách 2 : N&OxF8(8bit) hay N&OxFFF8(16bit) hay N&OxFFFFFFF8(32bit)
Vd : N=9 ---> 00001001
N&OxF8 : 00001000=8
Vậy M=8
*Câu này mình nghe nói có thể dùng 1 phép AND đơn giản mà ra luôn kết quả ( cách 2 cũng được nhưng chưa hay).
1d.
Tương tự câu trên.
N>>5
N<<5

1e.
N>>(n-1)
Kq=1 : số âm. Ngược lại, số dương

2a.
Thứ tự của bit được đánh từ phải sang trái, bắt đầu từ 0
Muốn biết bit thứ n là 0 hay 1 thì :
(N>>n)&1
Nếu kq=0 : bit thứ n là 0, kq=1 : bit thứ n là 1.
Vd : N : 00001101, cho biết bit 1 bật hay tắt.
N>>1 : 00000110
(N>>1)&1 : 00000000=0 ---> bit 1 của N là 0

***Câu 2b và 2c mình chưa nghĩ ra, ai có sáng kiến nào thì xin chỉ giáo. Còn câu 1b và 1c, mình hy vọng tìm được cách đơn giản hơn. Những giải thuật trên có trường hợp nào sai thì hãy nhắc nhở mình nhé.
Cảm ơn những ai đã xem bài viết này.

[reaper]

& and , | or, ^ xor, ~ đảo theo bit .
Câu 2b. Bật bit thứ M của N: Giả sử bạn muốn bật bít thứ 3 đi :Sử dụng OR nó với 100.
0000 0000 0010
---- ---- - 100
_____OR______
0000 0000 0110
Câu 2c. Đảo bit thứ M của N : Sử dụng phép XOR đi, chẳng hạn thế này nhé, bạn muốn đảo bit thứ tư đi :0 -> 1, bạn có thể chuyển dần 3bit cuối về đầu, lần lượt từng bit một, sau đó sử dụng phép XOR số N vừa xong với 1. Xong lại trả lại 3bit dầu về cuối cho nó : Ví dụ nhé :
0000 1000 0101 0110 đây là số N
0000 0100 0010 1011 đẩy xuống một bit, chuyển nó lên đầu
1000 0010 0001 0101 đẩy xuống một bit, chuyển nó lên đầu
1100 0001 0000 1010 đẩy xuống một bit, chuyển nó lên đầu
---- ---- ---- ---1 thực hiện XOR với 1
_______XOR_______
1100 0001 0000 1011 Kết quả
Giờ lại chuyển 3 bit đầu về cuối cho nó !
Hơi vất chút nhỉ !

[Kevin Hoang]

Câu 1
a. Sử dụng & là hay nhất đó, mấy cái sau bạn trình bày sẽ không hiệu quả
N&1 == 0 ==> Chẵn, còn lại là lẻ

b. Tương tự câu a.
Nếu (N&7) == 0 => chia hết cho 8, ngược lại thì không chia hết

c: Thử cách này xem: (Không quan tâm tới N có kiểu dữ liệu gì)
M = N>>3;
M <<= 3;

Câu d: Tương đương câu c
M = N>>5;
M <<= 5;

Câu c, d có thể làm như bạn đã chỉ, có điều là bạn phải xác định rõ kiểu dữ liệu của N, nếu không sẽ sai.

Câu 1.e: Nếu là kiểu 1 byte thì N&0x80, nếu là 2 byte thì N&0x8000, nếu là 4 byte thì N&0x800000. Kết quả khác không thì âm, bằng 0 thì dương (Tượng trưng thôi, chứ không chính xác)

Bài 2:
bit_M = 1 << M;

a. if(N & bit_M) == 0 thì tắt, khác không thì bật

b. N | bit_M

c. (N | bit_M) ^ N

Chỉ cần như thế thôi. Đảm bảo OK đó. Hì hì

[olat]

Cám ơn reaper và Dreaminess đã nhiệt tình chia sẻ ý tưởng.

-Câu 2b mình thấy ý tưởng của 2 bạn tương tự nhau nhưng dreaminess trình bày dễ hiểu hơn. Nhưng có vấn đề ở vd của reaper : bài đó là bật bít 2, không phải bít 3 (thứ tự bít được đánh từ 0 mà).

-Câu 2c của Dreaminess mình thấy làm như câu 2b là được rùi, chỉ cần đổi phép | thành ^ :
N^bit_M
Câu 2c của reaper mình chưa hiểu cho lắm.

Mọi người có thêm ý tưởng gì thì đề ra nhé. Sẵn đây mình đưa ra thêm vài đề bài để mọi người cùng làm:
3. cho biết ngày 14/4/2008 là thứ 2. Hãy viết chương trình nhập vào 1 bộ ngày, tháng, năm và cho biết ngày đó là thứ mấy.

4.Hãy nhập vào 1 bộ ngày, tháng, năm và cho biết ngày đó cách ngày hiện tại bao nhiêu ngày.

[Kevin Hoang]

Hì hì, câu 2c Dr làm sai, lúc đó nghĩ thế nào lại làm thế. Đúng như bạn nói, chỉ cần viết N^bit_M là được.

Mấy câu dưới thì Dr xin kiếu, không chơi kiểu tiện thể đó đâu. (Ghét kiểu xen lung tung lắm, đến khi xem lại không biết đâu mà lần cả)

[soujiro_seta]

Bạn Olat học lớp TH2D phải không? Mình là anbinhtrong nè, bài đó của thầy Huân đó. Nhớ nhắn lại cho tui nhé.
Tui xin góp ý câu 2c:
x=x^(1 << k) với k là vị trí của bit cần đảo.

[soujiro_seta]

Còn đối với ngày tháng năm, tui xin góp ý:
Trước tiên là xét sự chênh lệch của hai ngày tháng, sau đó dùng phép chia cho 7
Muốn xét sự chênh lệch của 2 ngày tháng, theo mình dễ nhất là xét ngày 1.1.1, rồi dùng 2 kết quả trừ nhau.
1 năm có 365 ngày, 4 năm có 1 năm nhuận, năm tận cùng là 00 thì phải chia hết cho 400 mới là năm nhuận. Như thế thôi.