fork download
copy 
  1. #include <iostream>     // Thư viện nhập xuất (cout, cin)
  2. #include <bitset>       // Dùng để in số ở dạng nhị phân (bit)
  3. #include <cstdint>      // Chứa các kiểu số nguyên có kích thước xác định (uint8_t, uint16_t, uint64_t)
  4. #include <iomanip>      // Dùng cho setw(), setfill(), hex, dec
  5. using namespace std;
  6.  
  7. // Hàm 1: Lấy giá trị của 1 bit tại vị trí cho trước
  8. bool lay_bit(uint64_t so, int vi_tri_bit);
  9.  
  10. // Hàm 2: In ra chuỗi 64 bit của 1 số nguyên 64-bit
  11. void in_day_bit(uint64_t so);
  12.  
  13. // Hàm 3: Đếm số bit '1' trong một số 64-bit
  14. int dem_bit_1(uint64_t so);
  15.  
  16. // Hàm 4: Gán giá trị cho 1 bit (0 hoặc 1) tại vị trí cho trước
  17. void gan_bit(uint64_t &so, int vi_tri_bit, bool gia_tri);
  18.  
  19. // Hàm 5: Hoán đổi giá trị của hai bit trong cùng một số
  20. void hoan_doi_bit(uint64_t &so, int bit_A, int bit_B);
  21.  
  22. // Hàm 6: Tìm độ dài dãy bit '1' liên tiếp dài nhất
  23. int do_dai_day_1_dai_nhat(uint64_t so);
  24.  
  25. // Hàm 7: Tìm dãy bit liên tiếp dài nhất có giá trị B (0 hoặc 1)
  26. // Kết quả mã hoá trong 16 bit: [0..5]=độ dài-1, [6..11]=vị trí bắt đầu, [12]=giá trị bit
  27. uint16_t tim_day_bit_dai_nhat(uint64_t so, bool gia_tri_bit_can_tim);
  28.  
  29. // Hàm 8: Quay trái K bit (bit rơi ra bên trái được đưa lại vào bên phải)
  30. uint64_t quay_trai(uint64_t so, int so_bit);
  31.  
  32. // Hàm 9: Quay phải K bit (bit rơi ra bên phải được đưa lại vào bên trái)
  33. uint64_t quay_phai(uint64_t so, int so_bit);
  34.  
  35. // Hàm 10: Đếm số lần thay đổi trạng thái giữa các bit (0→1 hoặc 1→0)
  36. int dem_so_lan_chuyen_trang_thai(uint64_t so);
  37.  
  38. // Hàm 11: Tìm vị trí cửa sổ (window) gồm W bit liên tiếp gần nhất
  39. // với dãy toàn 0 hoặc toàn 1
  40. int cua_so_gan_nhat(uint64_t so, int tong_so_bit, uint8_t do_rong_cua_so, bool bit_can_tim);
  41.  
  42. int main() {
  43.     uint64_t so;
  44.     cout << "Nhap vao mot so nguyen khong am (toi da 64-bit): ";
  45.     cin >> so;
  46.  
  47.     cout << "\nSo ban dau (dang nhi phan): ";
  48.     in_day_bit(so);
  49.     cout << endl;
  50.  
  51.     int lua_chon;
  52.     do {
  53.         cout << "\n========== MENU CHUC NANG ==========\n";
  54.         cout << "1. Lay gia tri cua mot bit\n";
  55.         cout << "2. Dem so bit '1'\n";
  56.         cout << "3. Gan gia tri cho mot bit (0 hoac 1)\n";
  57.         cout << "4. Hoan doi hai bit\n";
  58.         cout << "5. Do dai day bit '1' dai nhat\n";
  59.         cout << "6. Tim day bit dai nhat theo gia tri (0/1)\n";
  60.         cout << "7. Quay trai K bit\n";
  61.         cout << "8. Quay phai K bit\n";
  62.         cout << "9. Dem so lan chuyen trang thai (0↔1)\n";
  63.         cout << "10. Tim cua so gan nhat voi day toan 0/1\n";
  64.         cout << "0. Thoat\n";
  65.         cout << "===================================\n";
  66.         cout << "Chon chuc nang (0-10): ";
  67.         cin >> lua_chon;
  68.  
  69.         switch (lua_chon) {
  70.             case 1: {
  71.                 int vi_tri;
  72.                 cout << "Nhap vi tri bit can lay (0..63): ";
  73.                 cin >> vi_tri;
  74.                 cout << "Bit thu " << vi_tri << " = " << lay_bit(so, vi_tri) << endl;
  75.                 break;
  76.             }
  77.             case 2: {
  78.                 cout << "So luong bit '1' = " << dem_bit_1(so) << endl;
  79.                 break;
  80.             }
  81.             case 3: {
  82.                 int vi_tri;
  83.                 bool gia_tri;
  84.                 cout << "Nhap vi tri bit can gan (0..63): ";
  85.                 cin >> vi_tri;
  86.                 cout << "Nhap gia tri moi (0 hoac 1): ";
  87.                 cin >> gia_tri;
  88.                 gan_bit(so, vi_tri, gia_tri);
  89.                 cout << "Sau khi gan: ";
  90.                 in_day_bit(so);
  91.                 break;
  92.             }
  93.             case 4: {
  94.                 int a, b;
  95.                 cout << "Nhap hai vi tri bit can hoan doi: ";
  96.                 cin >> a >> b;
  97.                 hoan_doi_bit(so, a, b);
  98.                 cout << "Sau khi hoan doi: ";
  99.                 in_day_bit(so);
  100.                 break;
  101.             }
  102.             case 5: {
  103.                 cout << "Do dai day bit '1' dai nhat = " << do_dai_day_1_dai_nhat(so) << endl;
  104.                 break;
  105.             }
  106.             case 6: {
  107.                 bool gia_tri;
  108.                 cout << "Nhap gia tri bit can tim day (0 hoac 1): ";
  109.                 cin >> gia_tri;
  110.                 uint16_t thong_tin = tim_day_bit_dai_nhat(so, gia_tri);
  111.                 cout << "Thong tin ma hoa = 0x" << hex << setw(4) << setfill('0') << thong_tin << dec << endl;
  112.                 break;
  113.             }
  114.             case 7: {
  115.                 int k;
  116.                 cout << "Nhap so bit can quay trai: ";
  117.                 cin >> k;
  118.                 so = quay_trai(so, k);
  119.                 cout << "Sau khi quay trai: ";
  120.                 in_day_bit(so);
  121.                 break;
  122.             }
  123.             case 8: {
  124.                 int k;
  125.                 cout << "Nhap so bit can quay phai: ";
  126.                 cin >> k;
  127.                 so = quay_phai(so, k);
  128.                 cout << "Sau khi quay phai: ";
  129.                 in_day_bit(so);
  130.                 break;
  131.             }
  132.             case 9: {
  133.                 cout << "So lan chuyen trang thai (0↔1): " << dem_so_lan_chuyen_trang_thai(so) << endl;
  134.                 break;
  135.             }
  136.             case 10: {
  137.                 int tong_bit = 64;
  138.                 uint8_t rong;
  139.                 bool bit_tim;
  140.                 cout << "Nhap do rong cua so W: ";
  141.                 cin >> rong;
  142.                 cout << "Nhap bit can tim (0 hoac 1): ";
  143.                 cin >> bit_tim;
  144.                 cout << "Vi tri cua so gan nhat: " << cua_so_gan_nhat(so, tong_bit, rong, bit_tim) << endl;
  145.                 break;
  146.             }
  147.             case 0:
  148.                 cout << "Tam biet!\n";
  149.                 break;
  150.             default:
  151.                 cout << "Lua chon khong hop le. Thu lai!\n";
  152.         }
  153.     } while (lua_chon != 0);
  154.  
  155.     return 0;
  156. }
  157.  
  158. // ==================== ĐỊNH NGHĨA HÀM ====================
  159.  
  160. bool lay_bit(uint64_t so, int vi_tri_bit) {
  161.     return (so >> vi_tri_bit) & 1ULL;
  162. }
  163.  
  164. void in_day_bit(uint64_t so) {
  165.     cout << bitset<64>(so) << endl;
  166. }
  167.  
  168. int dem_bit_1(uint64_t so) {
  169.     int dem = 0;
  170.     for (int i = 0; i < 64; ++i)
  171.         if ((so >> i) & 1ULL) dem++;
  172.     return dem;
  173. }
  174.  
  175. void gan_bit(uint64_t &so, int vi_tri_bit, bool gia_tri) {
  176.     if (gia_tri)
  177.         so |= (1ULL << vi_tri_bit);   // Bật bit
  178.     else
  179.         so &= ~(1ULL << vi_tri_bit);  // Tắt bit
  180. }
  181.  
  182. void hoan_doi_bit(uint64_t &so, int bit_A, int bit_B) {
  183.     bool gia_tri_A = lay_bit(so, bit_A);
  184.     bool gia_tri_B = lay_bit(so, bit_B);
  185.     if (gia_tri_A != gia_tri_B) {
  186.         so ^= (1ULL << bit_A);
  187.         so ^= (1ULL << bit_B);
  188.     }
  189. }
  190.  
  191. int do_dai_day_1_dai_nhat(uint64_t so) {
  192.     int lon_nhat = 0, hien_tai = 0;
  193.     for (int i = 0; i < 64; ++i) {
  194.         if (lay_bit(so, i)) {
  195.             hien_tai++;
  196.             lon_nhat = max(lon_nhat, hien_tai);
  197.         } else hien_tai = 0;
  198.     }
  199.     return lon_nhat;
  200. }
  201.  
  202. uint16_t tim_day_bit_dai_nhat(uint64_t so, bool gia_tri_bit_can_tim) {
  203.     int lon_nhat = 0, bat_dau_tot = 0, hien_tai = 0, bat_dau_tam = 0;
  204.     for (int i = 0; i < 64; ++i) {
  205.         if (lay_bit(so, i) == gia_tri_bit_can_tim) {
  206.             if (hien_tai == 0) bat_dau_tam = i;
  207.             hien_tai++;
  208.             if (hien_tai > lon_nhat) {
  209.                 lon_nhat = hien_tai;
  210.                 bat_dau_tot = bat_dau_tam;
  211.             }
  212.         } else hien_tai = 0;
  213.     }
  214.  
  215.     uint16_t kq = 0;
  216.     kq |= (lon_nhat - 1) & 0x3F;          // [0..5]
  217.     kq |= (bat_dau_tot & 0x3F) << 6;      // [6..11]
  218.     kq |= (gia_tri_bit_can_tim ? 1 : 0) << 12; // [12]
  219.     return kq;
  220. }
  221.  
  222. uint64_t quay_trai(uint64_t so, int so_bit) {
  223.     return (so << so_bit) | (so >> (64 - so_bit));
  224. }
  225.  
  226. uint64_t quay_phai(uint64_t so, int so_bit) {
  227.     return (so >> so_bit) | (so << (64 - so_bit));
  228. }
  229.  
  230. int dem_so_lan_chuyen_trang_thai(uint64_t so) {
  231.     int dem = 0;
  232.     bool truoc = lay_bit(so, 0);
  233.     for (int i = 1; i < 64; ++i) {
  234.         bool hien_tai = lay_bit(so, i);
  235.         if (hien_tai != truoc) dem++;
  236.         truoc = hien_tai;
  237.     }
  238.     return dem;
  239. }
  240.  
  241. int cua_so_gan_nhat(uint64_t so, int tong_so_bit, uint8_t do_rong_cua_so, bool bit_can_tim) {
  242.     int vi_tri_tot = -1, chenh_lech_tot = 65;
  243.     for (int vi_tri = 0; vi_tri <= tong_so_bit - do_rong_cua_so; ++vi_tri) {
  244.         uint64_t cua_so = (so >> vi_tri) & ((1ULL << do_rong_cua_so) - 1);
  245.         int so_bit_1 = dem_bit_1(cua_so);
  246.         int chenh_lech = bit_can_tim ? (do_rong_cua_so - so_bit_1) : so_bit_1;
  247.         if (chenh_lech < chenh_lech_tot) {
  248.             chenh_lech_tot = chenh_lech;
  249.             vi_tri_tot = vi_tri;
  250.         }
  251.     }
  252.     return vi_tri_tot;
  253. }
  254.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nhap vao mot so nguyen khong am (toi da 64-bit): 
So ban dau (dang nhi phan): 0000000000000000011111111111110111011111110110111111100110101000


========== MENU CHUC NANG ==========
1. Lay gia tri cua mot bit
2. Dem so bit '1'
3. Gan gia tri cho mot bit (0 hoac 1)
4. Hoan doi hai bit
5. Do dai day bit '1' dai nhat
6. Tim day bit dai nhat theo gia tri (0/1)
7. Quay trai K bit
8. Quay phai K bit
9. Dem so lan chuyen trang thai (0↔1)
10. Tim cua so gan nhat voi day toan 0/1
0. Thoat
===================================
Chon chuc nang (0-10): Tam biet!
https://ideone.com/KZjoAN
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!