Cần giải thích cách dùng toán tử & trong c++

#1

gần đây mình thấy có nhiều bài code dùng lệnh như:

if(n&n-1) cout<<"yes";
else cout<<"no";

với

n+=n&(-n);

ai biết toán tử & trong 2 phần code ở trên hoạt động ra sao giải thích mình với mình tra gg thì nó kêu & là phép lấy và của số chuyển sang dạng nhị phân mà dùng cho 2 trường hợp trên thì lại k hiểu nó làm vậy có tác dụng gì

#2

ví dụ mình hỏi bạn câu này

cout<<“hello world”;

mình biết là lệnh này dùng để in ra chữ “hello world”, nhưng in ra chữ hello world đó để làm gì, bạn biết không?

2 Likes
#3

& là một trong những phép toán thao tác bit (bit operator) cơ bản.
Phép toán bit là phép toán gần nhất với mã máy.

Tất cả những gì bạn thao tác trên các thiết bị điện tử đều được chuyển thành tín hiệu 0 hoặc 1 để máy móc (CPU) có thể xử lý được.

1 Like
#4

Đây là trick để xem n có bằng 0, hay n là lũy thừa của 2 (2, 4, 8, etc).

n+=n&(-n)

Trick này thì tớ không biết 🤷 Cơ mà có trick

(n & -n) == n

là cách kiểm tra n có phải lũy thừa của 2 không. Java có dùng trick đó để cài đặt class Random.
Tớ không rõ nó có liên quan không :smile:

Hope it helps!

EDIT:
n & (-n) sẽ trả về LSB (least significant bit). Tớ vẫn chưa rõ ý đồ của việc cộng dồn đó là gì :smile:

EDIT 2:
Sẽ tốt hơn nếu cậu cho bọn tớ code và vấn đề mà đoạn code đó đang giải quyết. Có thêm context có thể sẽ giúp cậu hiểu lý do đằng sau cách viết đó.

5 Likes
#5 
#include<iostream>
#include<fstream>
#include<set>
using namespace std;
long long arrayx[100007]={0};
int check[100007]={0};
bool b[100007];
long long n,k;
void insertx(long long x,long long v)
{
    while(x<=n)
    {
        arrayx[x]+=v;
        x+=x&(-x);
    }
}
long long sumx(int x)
{
    long long r=0;
    while(x>0)
    {
        r+=arrayx[x];
        x&=(x-1);
    }
    return r;
}
main()
{
    long long x;
    ifstream fi("sumrecover.inp");
    ofstream fo("sumrecover.out");
    long long sum=0;
    fi>>n;
    for(int i=1;i<=n;i++)
    {
        fi>>check[i];
        insertx(i,check[i]);

    }
    long long m;
    fi>>m;
    long long b,y;
    for(int i=1;i<=m;i++)
    {
        fi>>b;
        if(b==0)
        {
            fi>>x>>k;
            insertx(x,k-check[x]);
            check[x]=k;
        }
        else
        {
            fi>>x>>y;
            if(x==1)k=0;
            else k=sumx(x-1);
            sum=sumx(y)-k;
            fo<<sum<<endl;
        }
    }

    fi.close();
    fo.close();
}

code đây bạn

#6

Come on, cậu nên cho bọn tớ cả đề bài chứ? :sweat:

#7

Sorry sorry :sweat_smile:
Mình tưởng bạn đã đạt tới cảnh giới đọc code tự suy ra đề :grin:

image
image1009×820 121 KB

#8

Oh, cảm ơn cậu đã nghĩ tốt về tớ nha :sweat_smile:

Đọc code DP kiểu này không dễ để giải thích đâu. Nhìn qua thì tớ cũng không giải thích được, mà tớ cũng không có nhiều thời gian lắm cho việc này. Vậy nên, tớ sẽ chỉ hướng cho cậu tự làm nhé!

  • Cậu nên thử chạy code từng bước một.
    Viết ra trên giấy, dùng debugger, etc. là cách để cậu có thể xem các giá trị thay đổi như thế nào qua từng bước.
  • Cậu cần phân tích những dữ liệu ở trên để thấy pattern. Kiểm tra xem nó đóng góp gì cho kết quả cuối cùng.
    Lúc đó, cậu sẽ nhìn ra được lý do của các lệnh ở trên mà cậu hỏi.

Nếu tìm ra thì chia sẻ cho mọi người biết nữa nhé! :sweat_smile:

Hope it helps!

2 Likes
#9

Code sử dụng CTDL sau: https://cp-algorithms.com/data_structures/fenwick.html

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?