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

Đây là ba bước thực hiện của thuật toán trên. )

int add_numbers(int a, int b)
{
int carry_out;

   while (b != 0)                // run loop untl carry is not zero
   {
     a = a ^ b;               // Sum of bits of x and y

     carry_out = a & b;       // carry_out contains common bits of a and b

    b = carry_out << 1;      // Carry is shifted by one and then XOR is performed to get the desired answer
   }

 return a;
}

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ử

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
7,
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
8 và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
9 thay vì sử dụng toán tử cộng bình thường (
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
0)

Bảng chủ đề

  1. Khái niệm cơ bản về hoạt động Bitwise
  2. Cộng hai số bằng toán tử bitwise
  3. Thêm bit bằng cách sử dụng đệ quy
  4. Độ phức tạp về thời gian và không gian của phép cộng bit
Khái niệm cơ bản về hoạt động Bitwise

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

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1 và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
2. Các
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1 và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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 bit

Các toán tử theo bit khác nhau được đưa ra bên dưới

Cách cộng hai số bằng toán tử bitwise trong C++

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

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
0 và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
2 số nhị phân tương đương với 25 là
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
3

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
4 số nhị phân tương đương với 14 là
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
5

1. Bitwise And - Bitwise và chỉ trả về 1 nếu cả hai bit là 1.

Cách cộng hai số bằng toán tử bitwise trong C++

2. Bitwise Hoặc - Bitwise hoặc trả về 1 nếu một trong hai bit là 1.
Cách cộng hai số bằng toán tử bitwise trong C++

3. Bitwise Not - Bitwise không trả về phần bù của bit.
Cách cộng hai số bằng toán tử bitwise trong C++

4. Bitwise Xor - Bitwise xor chỉ trả về 1 nếu một trong các bit bằng 0.
Cách cộng hai số bằng toán tử bitwise trong C++

5. Dịch chuyển trái theo từng bit
Cách cộng hai số bằng toán tử bitwise trong C++

Trong hình trên, chúng ta có thể thấy rằng ba
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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

Cách cộng hai số bằng toán tử bitwise trong C++

Trong hình trên, chúng ta có thể thấy rằng ba
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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ử bitwise

Trướ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.

Cách cộng hai số bằng toán tử bitwise trong C++

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

  • def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    8
  • def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    9
  • def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    70 tôi. e. nhị phân tương đương với 2

Và một điểm quan trọng khác cần lưu ý là khi chúng tôi nhận được

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
71,
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
2 sẽ được chuyển sang carry và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1 được giữ ở phía dưới

Bả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

Cách cộng hai số bằng toán tử bitwise trong C++

Từ bảng chân trị, chúng ta suy ra rằng

  • Biểu thức carry là
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    74
  • Biểu thức Tổng là
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    75

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

  1. Lấy hai số dương
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    0 và
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    1 làm đầu vào
  2. Sau đó kiểm tra xem số
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    1 có khác với số
    def Bitwise_add(a,b):
        if b == 0:
            return a
        else :
            return Bitwise_add(a^b , (a&b) << 1)
    
    1 không
    • Tìm giá trị
      def Bitwise_add(a,b):
          if b == 0:
              return a
          else :
              return Bitwise_add(a^b , (a&b) << 1)
      
      80 (______181)
    • Tìm giá trị
      def Bitwise_add(a,b):
          if b == 0:
              return a
          else :
              return Bitwise_add(a^b , (a&b) << 1)
      
      82 (
      def Bitwise_add(a,b):
          if b == 0:
              return a
          else :
              return Bitwise_add(a^b , (a&b) << 1)
      
      83) và lưu trữ nó trong biến
      def Bitwise_add(a,b):
          if b == 0:
              return a
          else :
              return Bitwise_add(a^b , (a&b) << 1)
      
      0
    • Sau đó chuyển carry sang trái 1-bit lưu nó vào
      def Bitwise_add(a,b):
          if b == 0:
              return a
          else :
              return Bitwise_add(a^b , (a&b) << 1)
      
      1
  3. một lần nữa quay lại bước 2
  4. Khi b trở thành 0, cuối cùng nó trả về tổng
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
4

.
Toàn bộ ý tưởng đằng sau đoạn mã này là giá trị thực được thêm lại với giá trị tổng. Vì vậy, những gì chúng ta làm là tìm giá trị của carry một cách riêng biệt bằng cách sử dụng biểu thức

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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.

Cách cộng hai số bằng toán tử bitwise trong C++

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.
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
81 trở thành
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1. Và cuối cùng, chúng ta có được tổng cần thiết của hai số.

Thêm bit bằng cách sử dụng đệ quy

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

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)

.
Trong mã này,

def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
89 là biểu thức tính tổng và
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1 i. e.
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
1 trở thành
def Bitwise_add(a,b):
    if b == 0:
        return a
    else :
        return Bitwise_add(a^b , (a&b) << 1)
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ận

Cá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.