Cách cộng hai số bằng toán tử bitwise trong C++
Giả sử chúng ta cần thêm hai bit. Chúng ta chỉ có thể sử dụng logic Half adder (đồ dành cho trẻ em). Trong một nửa bộ cộng, tổng số bit (S) được thực hiện bằng cách sử dụng bitwise XOR và việc mang bit (C) được thực hiện bằng cách sử dụng bit AND. Bây giờ tất cả những gì chúng ta phải làm là mở rộng hoặc tiếp tục sử dụng logic tương tự cho số lượng lớn bit. Bitwise XOR (^) của 'a' và 'b' cho tổng của 'a' và 'b' nếu 'a' và 'b' không có cùng một bit ở cùng một vị trí. Ví dụ 2^3 sẽ cho bạn 1 trong khi 2^5 sẽ cho 7 (Tự xem). Bây giờ chúng ta có thể tìm carry bằng cách sử dụng bitwise AND. Tất cả những gì chúng ta cần tính là (a & b) << 1 rồi cộng vào a^b. Đây sẽ là câu trả lời mong muốn của chúng tôi Show Đây là ba bước thực hiện của thuật toán trên. ) Trong bài viết này, chúng tôi đã giải thích cách cộng hai số dương bất kỳ bằng cách sử dụng toán tử bitwise như toán tử 7, 8 và 9 thay vì sử dụng toán tử cộng bình thường ( 0)Bảng chủ đề
Chúng tôi biết rằng máy tính lưu trữ tất cả các loại dữ liệu (video, tệp, ảnh, v.v. ) ở dạng số nhị phân 1 và 2. Các 1 và 2 này được gọi là các bit và các thao tác khác nhau có thể được thực hiện trên các số nhị phân này được gọi là các thao tác theo bitCác toán tử theo bit khác nhau được đưa ra bên dưới Hãy lấy một ví dụ và xem cách hoạt động của từng toán tử này. Xét 2 số thập phân 0 và 1 2 số nhị phân tương đương với 25 là 3 4 số nhị phân tương đương với 14 là 51. Bitwise And - Bitwise và chỉ trả về 1 nếu cả hai bit là 1. 2. Bitwise Hoặc - Bitwise hoặc trả về 1 nếu một trong hai bit là 1. 3. Bitwise Not - Bitwise không trả về phần bù của bit. 4. Bitwise Xor - Bitwise xor chỉ trả về 1 nếu một trong các bit bằng 0. 5. Dịch chuyển trái theo từng bit Trong hình trên, chúng ta có thể thấy rằng ba 1 đã được thêm vào bên phải i. e. sau bit Ít quan trọng nhất, gây ra sự dịch chuyển về phía bên trái. 6. Dịch chuyển sang phải theo chiều bit Trong hình trên, chúng ta có thể thấy rằng ba 1 đã được thêm vào bên trái i. e. sau bit quan trọng nhất, gây ra sự dịch chuyển về phía bên phải. Bây giờ vì chúng ta đã có ý tưởng về cách thức hoạt động của toán tử bitwise, hãy chuyển sang phép cộng hai số mà không cần toán tử cộng Cộng hai số bằng toán tử bitwiseTrước tiên, hãy xem cách phép cộng diễn ra ở cấp độ nhị phân và hiểu nó trước khi thử thực hiện với các toán tử bitwise. Phép cộng nhị phân khá giống với phép cộng thông thường. Từ ví dụ trên, chúng ta có thể hiểu rằng
Và một điểm quan trọng khác cần lưu ý là khi chúng tôi nhận được 71, 2 sẽ được chuyển sang carry và 1 được giữ ở phía dướiBảng chân trị sẽ giúp hiểu rõ hơn về cách phép cộng nhị phân diễn ra Từ bảng chân trị, chúng ta suy ra rằng
Sử dụng hai biểu thức trên, việc cộng hai số bất kỳ có thể được thực hiện như sau bước
4. 81 và sử dụng lại nó để tìm tổng. Chúng tôi tiếp tục làm điều này cho đến khi giá trị thực hiện trở thành 0. Một điểm quan trọng khác cần lưu ý ở đây là chúng ta dịch chuyển đòn gánh sang trái 1 bit. Đó là bởi vì giá trị thực được thêm vào bit tiếp theo thay vì bit hiện tại. Hãy nhìn vào hình ảnh này để hiểu rõ hơn. Chúng tôi tiếp tục lặp lại quy trình này cho đến khi giá trị thực hiện i. e. 81 trở thành 1. Và cuối cùng, chúng ta có được tổng cần thiết của hai số. Việc thêm các số bằng toán tử bitwise cũng có thể được thực hiện theo cách đệ quy. Logic tương tự diễn ra nhưng thay vì vòng lặp, chúng tôi sử dụng hàm đệ quy để thực hiện Phép cộng
. 89 là biểu thức tính tổng và 90 là biểu thức nhớ sau khi dịch chuyển. Vì vậy, nó được chuyển trực tiếp làm đầu vào cho hàm đệ quy. Và khi biểu thức carry trở thành 1 i. e. 1 trở thành 1, vòng lặp đệ quy dừng lại. Độ phức tạp về thời gian và không gian của phép cộng bitĐộ phức tạp thời gian của thuật toán là O(N), trong đó N là số bit trong các số. Độ phức tạp không gian của thuật toán là O(1) Cho một số M, số bit N bằng logM. Vì vậy, phép cộng hai số M không phải là phép toán O(1) theo thời gian không đổi. Phải mất log(M) thời gian. Cơ số của log là 2 Phần kết luậnCác hoạt động bitwise là một phần không thể thiếu của bất kỳ ngôn ngữ lập trình nào và hiểu rõ về chúng sẽ giúp bạn trở thành một lập trình viên giỏi hơn. Với bài viết này tại OpenGenus, bạn phải có ý tưởng mạnh mẽ về phép cộng sử dụng thao tác bitwise Phép cộng bitwise hoạt động như thế nào?Cộng nhị phân giống như phép cộng thông thường hàng ngày của bạn (cộng thập phân), ngoại trừ việc nó mang giá trị 2 thay vì giá trị 10. For example: in decimal addition, if you add 8 + 2 you get ten, which you write as 10; in the sum this gives a digit 0 and a carry of 1.
Là bitwise hoặc bằng bổ sung?Bất cứ khi nào phép cộng theo bit thêm nhiều hơn 1 (vì nguồn có chúng hoặc giá trị mang từ nơi khác cũng là 1), thì giá trị mang được tạo ra và một nơi ảnh hưởng đến nơi khác. Miễn là trong một phép cộng có nhiều nhất một phép cộng 1, thì mọi thứ cũng giống như theo chiều bit hoặc.
Làm cách nào để nhân hai số bằng toán tử bitwise trong C?Lập trình C và C nhúng thành thạo- Vừa học vừa làm
. Phép nhân hai số x, y có thể viết dưới dạng x * y = (x * 2) * (y / 2) nếu y chẵn khác nó bằng x * y = (x * y) * (y / 2) . The left shift (<<) operator is used for the multiplication whereas the right shift (>>) is used for the division. The multiplication of two numbers x, y can be written as x * y = (x * 2) * (y / 2) if y is even else it's equal to x * y = (x * y) * (y / 2) + x.
Làm cách nào để cộng hai số mà không cần sử dụng toán tử trong C?Đó là một câu hỏi mẹo. Chúng ta có thể dùng printf() để tìm tổng của hai số vì printf() trả về số ký tự được in. Trường chiều rộng trong printf() có thể được sử dụng để tìm tổng của hai số. Chúng ta có thể sử dụng '*' cho biết chiều rộng tối thiểu của đầu ra. |