给定一个数字n，任务是在不使用+、-、*、/和%运算符的情况下检查该数字是否为4的倍数。 例如：
null
Input: n = 4 Output - Yes n = 20 Output - Yes n = 19 Output - No
方法1（使用XOR） n>1的一个有趣的事实是，我们对从1到n的所有数字进行异或运算，如果结果等于n，那么n是4的倍数，否则不是。
C++
// An interesting XOR based method to check if // a number is multiple of 4. #include<bits/stdc++.h> using namespace std; // Returns true if n is a multiple of 4. bool isMultipleOf4( int n) { if (n == 1) return false ; // Find XOR of all numbers from 1 to n int XOR = 0; for ( int i = 1; i <= n; i++) XOR = XOR ^ i; // If XOR is equal n, then return true return (XOR == n); } // Driver code to print multiples of 4 int main() { // Printing multiples of 4 using above method for ( int n=0; n<=42; n++) if (isMultipleOf4(n)) cout << n << " " ; return 0; } |
JAVA
// An interesting XOR based method to check if // a number is multiple of 4. class Test { // Returns true if n is a multiple of 4. static boolean isMultipleOf4( int n) { if (n == 1 ) return false ; // Find XOR of all numbers from 1 to n int XOR = 0 ; for ( int i = 1 ; i <= n; i++) XOR = XOR ^ i; // If XOR is equal n, then return true return (XOR == n); } // Driver method public static void main(String[] args) { // Printing multiples of 4 using above method for ( int n= 0 ; n<= 42 ; n++) System.out.print(isMultipleOf4(n) ? n : " " ); } } |
Python 3
# An interesting XOR based # method to check if a # number is multiple of 4. # Returns true if n is a # multiple of 4. def isMultipleOf4(n): if (n = = 1 ): return False # Find XOR of all numbers # from 1 to n XOR = 0 for i in range ( 1 , n + 1 ): XOR = XOR ^ i # If XOR is equal n, then # return true return (XOR = = n) # Driver code to print # multiples of 4 Printing # multiples of 4 using # above method for n in range ( 0 , 43 ): if (isMultipleOf4(n)): print (n, end = " " ) # This code is contributed # by Smitha |
C#
// An interesting XOR based method // to check if a number is multiple // of 4. using System; class GFG { // Returns true if n is a // multiple of 4. static bool isMultipleOf4( int n) { if (n == 1) return false ; // Find XOR of all numbers // from 1 to n int XOR = 0; for ( int i = 1; i <= n; i++) XOR = XOR ^ i; // If XOR is equal n, then // return true return (XOR == n); } // Driver method public static void Main() { // Printing multiples of 4 // using above method for ( int n = 0; n <= 42; n++) { if (isMultipleOf4(n)) Console.Write(n+ " " ); } } } // This code is contributed by Smitha. |
PHP
<?php // PHP program to check if // a number is multiple of 4. // Returns true if n is // a multiple of 4. function isMultipleOf4( $n ) { if ( $n == 1) return false; // Find XOR of all // numbers from 1 to n $XOR = 0; for ( $i = 1; $i <= $n ; $i ++) $XOR = $XOR ^ $i ; // If XOR is equal n, // then return true return ( $XOR == $n ); } // Driver Code // Printing multiples of 4 // using above method for ( $n = 0; $n <= 42; $n ++) if (isMultipleOf4( $n )) echo $n , " " ; // This code is contributed by Ajit ?> |
Javascript
<script> // Javascript program of interesting XOR based method to check if // a number is multiple of 4. // Returns true if n is a multiple of 4. function isMultipleOf4(n) { if (n == 1) return false ; // Find XOR of all numbers from 1 to n let XOR = 0; for (let i = 1; i <= n; i++) XOR = XOR ^ i; // If XOR is equal n, then return true return (XOR == n); } // Driver Code // Printing multiples of 4 using above method for (let n = 0; n <= 42; n++) document.write(isMultipleOf4(n) ? n : " " ); // This code is contributed by avijitmondal1998. </script> |
输出：
0 4 8 12 16 20 24 28 32 36 40
时间复杂度：O（n）
辅助空间：O（1）
这是怎么回事？ 当我们对数字进行异或运算时，我们得到0作为4的倍数之前的异或值。这会在4的每一个倍数之前不断重复。
Number Binary-Repr XOR-from-1-to-n1 1 [0001]2 10 [0011]3 11 [0000]
方法2（使用位移位运算符） 想法是使用>>删除最后两位，然后使用<
C++
// An interesting XOR based method to check if // a number is multiple of 4. #include<bits/stdc++.h> using namespace std; // Returns true if n is a multiple of 4. bool isMultipleOf4( long long n) { if (n==0) return true ; return (((n>>2)<<2) == n); } // Driver code to print multiples of 4 int main() { // Printing multiples of 4 using above method for ( int n=0; n<=42; n++) if (isMultipleOf4(n)) cout << n << " " ; return 0; } |
JAVA
// An interesting XOR based method to check if // a number is multiple of 4. class Test { // Returns true if n is a multiple of 4. static boolean isMultipleOf4( long n) { if (n== 0 ) return true ; return (((n>> 2 )<< 2 ) == n); } // Driver method public static void main(String[] args) { // Printing multiples of 4 using above method for ( int n= 0 ; n<= 42 ; n++) System.out.print(isMultipleOf4(n) ? n : " " ); } } |
C#
// An interesting XOR based method to // check if a number is multiple of 4. using System; class GFG { // Returns true if n is a multiple // of 4. static bool isMultipleOf4( int n) { if (n == 0) return true ; return (((n >> 2) << 2) == n); } // Driver code to print multiples // of 4 static void Main() { // Printing multiples of 4 using // above method for ( int n = 0; n <= 42; n++) if (isMultipleOf4(n)) Console.Write(n + " " ); } } // This code is contributed by Anuj_67 |
PHP
<?php // PHP program to check if // a number is multiple of 4. // Returns true if n is // a multiple of 4. function isMultipleOf4( $n ) { if ( $n == 0) return true; return ((( $n >> 2) << 2) == $n ); } // Driver Code // Printing multiples of 4 // using above method for ( $n = 0; $n <= 42; $n ++) if (isMultipleOf4( $n )) echo $n , " " ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // An interesting XOR based method to // check if a number is multiple of 4. // Returns true if n is a multiple // of 4. function isMultipleOf4(n) { if (n == 0) return true ; return (((n >> 2) << 2) == n); } // Printing multiples of 4 using // above method for (let n = 0; n <= 42; n++) if (isMultipleOf4(n)) document.write(n + " " ); </script> |
输出：
0 4 8 12 16 20 24 28 32 36 40
时间复杂度：O（1）
辅助空间：O（1）
我们可以看到，求4的重数的主要思想是检查给定数字的至少两个有效位。我们知道，对于任何偶数，最低有效位总是零（即0）。类似地，对于4的倍数的任何数字，至少有两个有效位为零。在同样的逻辑下，对于任何8的倍数，至少有三个有效位为零。这就是为什么我们可以使用AND运算符（&）以及其他操作数0x3来求4的重数。 本文由 萨希尔·查布拉（杀手） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
