解决问题的低级技巧

Posted on 2022-05-30

udx4lustuvofapicmtkw.png

使用最流行的低级技术之一解决编程问题

位操作和位运算符

当你用你最喜欢的编程语言编译任何东西时，它都会被转换成机器代码

有一个非常令人印象深刻的技巧可以帮助您解决问题?

什么是按位运算符？

  1. C 或 C++ 中的&（按位与）将两个数字作为操作数，并对两个数字的每一位进行 AND。仅当两个位都为 1 时，AND 的结果才为 1。
  2. 该| C 或 C++ 中的（按位或）将两个数字作为操作数，并对两个数字的每一位进行 OR。如果两位中的任何一位为 1，则 OR 的结果为 1。
  3. C 或 C++ 中的^（按位 XOR）将两个数字作为操作数，并对两个数字的每一位进行 XOR。如果两个位不同，则异或的结果为 1。
  4. C 或 C++ 中的<<（左移）需要两个数字，左移第一个操作数的位，第二个操作数决定要移位的位数。
  5. C 或 C++ 中的>>（右移）需要两个数字，右移第一个操作数的位，第二个操作数决定要移位的位数。
  6. C 或 C++ 中的~（按位非）取一个数字并将其所有位取反。

让我们通过示例了解它是如何工作的

请记住，您将处理的每个数字都将转换为二进制
如果你熟悉数字电路，就会很容易理解它们是如何工作的

示例 #1

 int main (){ // a = 5(00000101), b = 9(00001001) int a = 5 , b = 9 ; // The result is 00000001 cout << "a = " << a << "," << " b = " << b << endl ; cout << "a & b = " << ( a & b ) << endl ; }
  • 让我们放一个示例规则 0 为假 1 为真每个数字在打印时都会再次转换为小数。

解释#1

& 运算符的工作方式就像这两种情况都是 1 一样，它将返回 1
所以
1&1 = 1
1&0 = 0
0&1 = 0
0&0 = 0

示例 #1

a = 5 ，二进制为 00000101

b = 9 ，二进制为 00001001

所以我们取每个数字并应用我们的 & 规则

1 & 1 = 1，以此类推..

所以结果将是 a & b = 00000001

示例 #2

 // The result is 00001101 cout << "a | b = " << ( a | b ) << endl ;

解释#2

该|如果其中一种情况为 1，则操作员工作，它将返回 1
1|1 = 1
1|0 = 1
0|1 = 1
0|0 = 0

示例 #2

a = 5 ，二进制为 00000101

b = 9 ，二进制为 00001001

所以我们取每个数字并应用我们的 |规则

1 | 1 = 1，以此类推..

所以结果将是 | b = 00001101

示例#3

 // The result is 00001100 cout << "a ^ b = " << ( a ^ b ) << endl ;

解释#3

^ 运算符有点混乱，如果两个数字不同，它将返回 1
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

示例#3

a = 5，二进制为 00000101

b = 9，二进制为 00001001

所以我们取每个数字并应用我们的 ^ 规则

1 ^ 1 = 1，以此类推..

所以结果将是十进制的 a ^ b = 00001100 = 12

示例 #4

 // The result is 11111010 cout << "~a = " << ( ~ a ) << endl ;

解释#4

~ 运算符得到与数字相反的结果，
~1 = 0
~0 = 1

示例 #4

a = 5，二进制为 00000101

所以我们取每个数字并应用我们的 ~ 规则

~1 = 0 ，依此类推..

所以结果将是 ~a = 11111010 = -6十进制用基本规则将其转换为十进制太难了，所以搜索 2 的补码、1 的补码和有符号幅度

请记住 – 最后一个左数字表示它是正数 = 0 还是负数 = 1，当您应用此运算符时，如果您想获得数字的负值，您应该在结果中添加 +1

示例#5

 // b=9 (00001001) // The result is 00010010 cout << "b << 1" << " = " << ( b << 1 ) << endl ; // The result is 00000100 cout << "b >> 1 " << "= " << ( b >> 1 ) << endl ;

解释#5

<< 运算符将位模式 n 次移到左移，在我们的例子中 n=1 并在数字末尾附加 0，左移相当于将位模式乘以$2^n$
（如果我们要移动 n 位）。
1 = 00000001
1 << 1 = 00000010 = 2 = $(1*2^1)$ 等等..
在示例中
9 << 1 = 00010010 = $(9 * 2^1)$ = 18

>> 运算符将位模式 n 次向右移动，在我们的例子中 n=1 并在数字末尾附加 1，左移相当于将位模式除以 $2^n$
（如果我们要移动 n 位）。请记住，在这种情况下，二进制没有浮点数
4 = 00000100
4 >> 1 = 00000010 = 2 = $(4/2^1)$

5 = 00000101
6 >> 1 = 00000010 = 2 = $(5/2^1)$ 十进制等等..

在示例中

9 >> 1 = 00000100 = 4 = $( 9/2^n )$ 十进制

让我们知道位操作如何与示例一起工作

以及为什么对优化的解决方案如此有帮助，它就像魔法一样工作?

让我们从一个简单的例子开始

我们想知道 x 是否是 2 的幂

执行

bool isPowerOfTwo ( int x ) { if ( x == 0 ) return false ; else { while ( x % 2 == 0 ) x /= 2 ; return ( x == 1 ); } }

上述代码的时间复杂度为 O(log N)

有最优方法吗？

使用位操作可以解决相同的问题。

考虑一个数字 x，我们需要检查它是否是 2 的幂。

现在考虑 (x-1) 的二进制表示。

(x-1) 将具有与 x 相同的所有位，除了 x 中最右边的 1 和最右边 1 右侧的所有位。

让 x = 4 = (100)2 x – 1 = 3 = (011)2

让 x = 6 = (110)2 x – 1 = 5 = (101)2

这些例子可能看起来并不明显，但 (x-1) 的二进制表示可以通过简单地将 x 中最右边 1 的所有位翻转并包括最右边的 1 来获得。

现在想想 x & (x-1)。

x & (x-1) 将具有等于 x 的所有位，除了 x 中最右边的 1。

设 x = 4 = (100)2 x – 1 = 3 = (011)2 x & (x-1) = 4 & 3 = (100)2 & (011)2 = (000)2

令 x = 6 = (110)2 x – 1 = 5 = (101)2 x & (x-1) = 6 & 5 = (110)2 & (101)2 = (100)2

在 x= 6 中，6 不是 2 的幂，所以当 x & (x-1) = (100)2 表示这不是我们想要的

数字是 2 的幂的属性是，它们在二进制表示中设置了一位且只有一位。

如果该数字既不是零也不是 2 的幂，那么它将在多个位置有 1。因此，如果 x 是 2 的幂，则 x & (x-1) 将为 0。

执行：

 bool isPowerOfTwo ( int x ) { // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not return ( x && ! ( x & ( x - 1 ))); }

并且上述代码的时间复杂度为 O(1)

另一个很难看出位操作有多强大的例子

给定一个字符串words
, 返回最大值
length(word[i]) * length(word[j])
这两个词不共享共同的字母
.如果不存在这两个词，则返回0

想法是为每个字符串创建一个位掩码，并将其与其他字符串的位掩码进行比较。

位掩码说明

–假设我们有三个字符串“abc”、“def”和“abde”，这些字符串对应的位掩码将是“111”、“111000”和“11011”。如何？

对于每个字符，我们需要找到需要在位掩码中设置 1 的索引。因此，对于字符“a”，索引将为 0，对于“b”，它将为 1，对于“c”，它将为 2，依此类推。

通过将每个字符减去’a’ Ex. 可以很容易地找到索引。

 'a' - 'a' = 0 'b' - 'a' = 1 'c' - 'a' = 2

下一步是将索引值左移 1。

 for 'a' , index will be 0 1 << 0 = 1 'b' , index will be 1 1 << 1 = 10 'c' , index will be 2 1 << 2 = 100

移位后，最后一步是将当前字符的移位值与当前字符串的位掩码进行或运算。因此，如果我们对字符“a”、“b”和“c”的移位值进行或运算。

001 | 010 | 100 = 111

检查共同字符 –如果两个字符串 s1 和 s2 有共同字符，那么它们在位掩码中的相同索引处将有 1，如果我们对 s1 和 s2 的位掩码进行 AND，它将导致值大于 0。

 bitmask [ s1 ] & bitmask [ s2 ] = 0 , if no common characters > 0 , otherwise Ex . bitmask of "abc" and "def" is 111 and 111000 , respectively . 111 & 111000 = 0 , hence no common characters bitmask of "abc" and "abde" is 111 and 11011 , respectively . 111 & 11011 = 00011 > 0 , hence common characters found

最后，代码–

 class Solution { public int maxProduct ( String [] words ) { int n = words . length ; int [] bitmask = new int [ n ]; int max = 0 ; for ( int i = 0 ; i < n ; i ++) { // Calculate bitmask for current word for ( int j = 0 ; j < words [ i ]. length (); j ++) { // index will be - for a -> 0, b -> 1, c -> 2 and so on int index = words [ i ]. charAt ( j ) - 'a' ; // left shift 1 by index and OR it with the current bitmask bitmask [ i ] |= ( 1 << index ); } // Compare bitmask of current string with previous strings bitmask for ( int j = 0 ; j < i ; j ++) { /* If there is a 1 at the same index of current string {i} and {j}, then bitmask of i and j string will result in a number greater than 0, else it will result in 0 */ if ( ( bitmask [ i ] & bitmask [ j ]) == 0 ) max = Math . max ( max , words [ i ]. length ()* words [ j ]. length ()); } } return max ; } }

时间复杂度 = O(n.(k+n))

原文： https://dev.to/mahmoudgalal/low-level-trick-to-solve-problems-69o