DSA - 位运算算法

上一页
下一页

位运算算法介绍

位运算算法是指控制数据个体位操作的算法。这些算法主要用于提高运算速度和内存效率，尤其是在处理大型数据集时。

什么是位？

计算机无法理解人类语言，需要使用位编码的数据。这里，位是计算机中最小的信息单位。它由二进制数字表示，只有两个值，即0和1。它的其他表示形式为是或否，真或假，以及开或关。

位操作（运算符）

位操作是一种技术，它涉及对数据的个体位执行低级操作，例如加密、切换、移位或屏蔽它们。对位执行的操作称为位运算。此操作需要一个或两个操作数，它们首先被转换为二进制，然后将运算符应用于每对相应的位。此操作的结果也是一个二进制数。

位操作可用于各种目的，例如：

  • 它可用于实现需要直接访问数据二进制表示的低级算法或数据结构，例如加密、压缩、哈希或密码学。

  • 它可以通过减少执行给定任务（例如算术、逻辑或位计数）所需的指令或字节数来优化性能或内存使用。

  • 位操作还用于操作使用特定位来控制设备行为或状态的硬件寄存器或设备驱动程序。

为了执行位操作，我们使用各种位运算符。它们解释如下：

按位与运算符 (&)

单个“与”符号(&)表示按位与运算符。它接受两个操作数，如果两个位都是1，则返回1，否则返回0。

AND Operation

示例

在以下示例中，我们将说明各种编程语言中的与运算。

C C++ Java Python
#include <stdio.h>
int main() {
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne & valTwo;
   printf("Result of AND operation: %d\n", output); 
   return 0;
}

#include <iostream>
using namespace std;
int main()
{
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne & valTwo;
   cout << "Result of AND operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int valOne = 8;
      int valTwo = 9;
      int output = valOne & valTwo;
      System.out.println("Result of AND operation: " + output);
   }
}

valOne = 8
valTwo = 9
output = valOne & valTwo
print("Result of AND operation:", output)

输出

Result of AND operation: 8

按位或运算符 (|)

单个管道符号(|)表示按位或运算符。它接受两个操作数作为参数值，如果任一位为1，则返回1，否则返回0。

OR Operation

示例

以下示例演示了不同编程语言中按位或运算符的工作原理。

C C++ Java Python
#include <stdio.h>
int main() {
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne | valTwo;
   printf("Result of OR operation: %d\n", output); 
   return 0;
}

#include <iostream>
using namespace std;
int main() {
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne | valTwo;
   cout << "Result of OR operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int valOne = 8;
      int valTwo = 9;
      int output = valOne | valTwo;
      System.out.println("Result of OR operation: " + output);
   }
}

valOne = 8
valTwo = 9
output = valOne | valTwo
print("Result of OR operation:", output)

输出

Result of OR operation: 9

按位异或运算符 (^)

按位异或运算符由插入符号(^)表示。它也接受两个操作数，如果位不同，则返回1，否则返回0。

XOR Operation

示例

以下示例显示了按位异或运算符的工作原理。

C C++ Java Python
#include <stdio.h>
int main() {
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne ^ valTwo;
   printf("Result of XOR operation: %d\n", output); 
   return 0;
}

#include <iostream>
using namespace std;
int main() {
   int valOne = 8;
   int valTwo = 9; 
   int output = valOne ^ valTwo;
   cout << "Result of XOR operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int valOne = 8;
      int valTwo = 9;
      int output = valOne ^ valTwo;
      System.out.println("Result of XOR operation: " + output);
   }
}

valOne = 8
valTwo = 9
output = valOne ^ valTwo
print("Result of XOR operation:", output)

输出

Result of XOR operation: 1

按位非运算符 (~)

按位非运算符由单个波浪号(~)表示。它接受1或0作为操作数，并返回该操作数的补码，这意味着它将每个位从0翻转到1，从1翻转到0。

NOT Operation

示例

以下示例说明了各种编程语言中非运算符的工作原理。

C C++ Java Python
#include <stdio.h>
int main() {
   int value = 0;
   int output = ~value;
   printf("Result of NOT operation: %d\n", output); 
   return 0;
}

#include <iostream>
using namespace std;
int main() {
   int value = 0;
   int output = ~value;
   cout << "Result of NOT operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int value = 0;
      int output = ~value;
      System.out.println("Result of NOT operation: " + output);
   }
}

value = 0
output = ~value
print("Result of NOT operation:", output)

输出

Result of NOT operation: -1

左移运算符 (<<)

双左箭头符号(<<)表示左移运算符。它用于将操作数的指定位向左移动给定数量的位置。它用零填充空缺的位。

Left Shift Operation

示例

在以下示例中，我们将说明各种编程语言中的左移操作。

C C++ Java Python
#include <stdio.h>
int main() {
   int value = 11;
   // int to binary conversion
   char newVal[5];
   for(int i = 3; i >= 0; i--) {
      newVal[3-i] = ((value >> i) & 1) ? '1' : '0';
   }
   newVal[4] = '\0';
   int output = value << 2; 
   printf("Binary representation of value: %s\n", newVal);
   printf("Result of Left-Shift operation: %d\n", output); 
   return 0;
}

#include <iostream>
#include <bitset>
using namespace std;
int main() {
   int value = 11;
   // int to binary conversion
   string newVal = bitset<4>(value).to_string(); 
   int output = value << 2; 
   cout << "Binary representation of value: " << newVal << endl;
   cout << "Result of Left-Shift operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int value = 11;
      // int to binary conversion
      String newVal = Integer.toBinaryString(value);
      int output = value << 2;
      System.out.println("Binary representation of value: " + newVal);
      System.out.println("Result of Left-Shift operation: " + output);
   }
}

value = 11
# int to binary conversion
newVal = format(value, '04b')
output = value << 2
print("Binary representation of value:", newVal)
print("Result of Left-Shift operation:", output)

输出

Binary representation of value: 1011
Result of Left-Shift operation: 44

右移运算符 (>>)

双右箭头符号(>>)表示右移运算符。它用于将操作数的指定位向右移动给定数量的位置。它用零或符号位填充空缺的位（取决于操作数是有符号的还是无符号的）。

Right Shift Operation

示例

以下示例演示了各种编程语言中右移操作的工作原理。

C C++ Java Python
#include <stdio.h>
int main() {
   int value = 11;
   // int to binary conversion
   char newVal[5];
   for(int i = 3; i >= 0; i--) {
      newVal[3-i] = ((value >> i) & 1) ? '1' : '0';
   }
   newVal[4] = '\0';
   int output = value >> 2; 
   printf("Binary representation of value: %s\n", newVal);
   printf("Result of Right-Shift operation: %d\n", output); 
   return 0;
}

#include <iostream>
#include <bitset>
using namespace std;
int main() {
   int value = 11;
   // int to binary conversion
   string newVal = bitset<4>(value).to_string(); 
   int output = value >> 2; 
   cout << "Binary representation of value: " << newVal << endl;
   cout << "Result of Right-Shift operation: " << output << endl; 
   return 0;
}

public class Main {
   public static void main(String[] args) {
      int value = 11;
      // int to binary conversion
      String newVal = Integer.toBinaryString(value);
      int output = value >> 2;
      System.out.println("Binary representation of value: " + newVal);
      System.out.println("Result of Right-Shift operation: " + output);
   }
}

value = 11
# int to binary conversion
newVal = format(value, '04b')
output = value >> 2
print("Binary representation of value:", newVal)
print("Result of Right-Shift operation:", output)

输出

Binary representation of value: 1011
Result of Right-Shift operation: 2
打印页面
上一页
下一页
广告