Từ 1 tới 7 trên tổng số 7 kết quả

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

  1. #1
    No Avatar
    olat Khách

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

    Đâ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.
    Đã được chỉnh sửa lần cuối bởi olat : 13-04-2008 lúc 09:19 PM.

  2. #2
    Ngày gia nhập
    04 2008
    Bài viết
    20

    & 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ỉ !

  3. #3
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    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ì
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  4. #4
    No Avatar
    olat Khách

    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.
    Đã được chỉnh sửa lần cuối bởi olat : 14-04-2008 lúc 10:01 AM.

  5. #5
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    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ả)
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  6. #6
    Ngày gia nhập
    02 2008
    Bài viết
    31

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

    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.
    Số phận nghiệt ngã có thể khiến bạn bỏ cuộc, mọi người có thể nói với bạn là không thể- nhưng chính bạn mới là người quyết định có bỏ cuộc hay không- cho dù bất kì điều gì xảy ra.

  7. #7
    Ngày gia nhập
    02 2008
    Bài viết
    31

    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.
    Số phận nghiệt ngã có thể khiến bạn bỏ cuộc, mọi người có thể nói với bạn là không thể- nhưng chính bạn mới là người quyết định có bỏ cuộc hay không- cho dù bất kì điều gì xảy ra.

Các đề tài tương tự

  1. Lập trình C++ trong visual studio có cách nào để dùng winform mà vẫn dùng cách viết trên c++ được ?
    Gửi bởi homgiaouoc trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 08-10-2013, 12:50 PM
  2. Cách dùng biến khi người dùng mở 1 trang trên 2 tab khác nhau
    Gửi bởi tuanngocpt trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 1
    Bài viết cuối: 24-08-2013, 08:28 AM
  3. giải bài toán Tháp Hà Nội dùng thuật đệ quy trên nền Visuastudio C#
    Gửi bởi anhhai6822 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 5
    Bài viết cuối: 07-04-2013, 06:46 PM
  4. MS SQL với C# So sánh tốc độ khi dùng CURSOR ở SQL với việc dùng for trên code c# khi cập nhật hàng loạt
    Gửi bởi david_tonny trong diễn đàn Thắc mắc Microsoft SQL Server & Microsoft Access
    Trả lời: 1
    Bài viết cuối: 23-04-2012, 11:46 AM
  5. Tìm kiếm trên file! Tìm kiếm xâu mẫu dùng giải thuật Naive | Giúp mình code sai ở đâu
    Gửi bởi totoise trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 19-04-2009, 08:22 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn