python

您所在的位置：网站首页 › 2的2004次方被7除的所得余数 › python

python

2023-07-04 09:23| 来源: 网络整理| 查看: 265

给定一个整数 n，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

n 的范围大于等于0.

以下解法都是基于 n 为 2 的幂次方的前提下，进行的，因为 x 的四次方幂一定是 x 的二次方幂，而 x 的二次方幂不一定是 x 的四次方幂。

$x^{4} = x^{2\times2}$

解法1： def is_power_of_four(): # 导入random函数生成随机数 import random # 生成一个范围在 0 到 11 之间的随机偶数 #y = random.randrange(0, 10, 2) # 生成一个范围在 1 到 10 之间的随机整数 n = random.choice([1, 4, 16, 64]) #n = random.choice([2, 8, 32, 128]) #n = random.randint(0, 10) print(n) # 4的幂次方一定是2的幂次方，但是4的幂次方所占的二进制位数都是奇数。例如： 1(1) 100(4) 10000(16) 1000000(64) # (1 & n.bit_length()) 当 n.bit_length() 为奇数时，计算结果为 1(真)。 if (n > 0) & ((n & -n) == n) & (1 & n.bit_length()): print("true") else: print("false") # 调用函数，输出结果 is_power_of_four() 解法2：通过取模性质 # 导入random函数生成随机数 import random def is_power_of_four(): # 生成一个范围在 0 到 11 之间的随机偶数 #y = random.randrange(0, 10, 2) # 生成一个范围在 1 到 10 之间的随机整数 #n = random.choice([1, 4, 16, 64]) n = random.choice([2, 8, 32, 128]) #n = random.randint(0, 10) print(n) # 2**N % 3 的余为 1 时N为偶数，余为 2 时N为奇数。4**N = 2**(2*N),所以当 n % 3 为 1 时，且 n 为 2的幂次方，则n为4的幂次方。 if (n > 0) and ((n & -n) == n) and n % 3 == 1: return "true" else: return "false" # 调用函数，输出结果 print(is_power_of_four()) 解法3：通过二进制中 1 的位置 # 导入random函数生成随机数 import random def is_power_of_four(): # 生成一个范围在 0 到 11 之间的随机偶数 #y = random.randrange(0, 10, 2) # 生成一个范围在 1 到 10 之间的随机整数 #n = random.choice([1, 4, 16, 64]) #n = random.choice([2, 8, 32, 128]) n = random.randint(0, 10) print(n) # 4的幂次方一定是2的幂次方，但是4的幂次方所占的二进制位数都是奇数。例如： 1(1) 100(4) 10000(16) 1000000(64) # 当4的幂次方与(&) 101010...(0xaaa...) 等于0。 # 因为4 的幂次方它的二进制中1的位置在奇数位，而 101010...(0xaaa...) 它的1的位置都在偶数位。它俩与(&)的结果是0. # 这里的n的大小是有限制的, 0 0) and (n & (n - 1) == 0) and (n & 0xaaaaaaaa == 0): return True else: return False # 调用函数，输出结果 print(is_power_of_four()) 扩展 - 1：

同余是初等数论中重要的概念，通常用符号 $a\equiv b \pmod{m}$ 表示，意思是“a与b模m同余”，或者说“a和b除以m所得的余数相等”。

具体来说，如果两个整数a和b除以正整数m所得的余数相等，即 $a\bmod m = b\bmod m$ ，则称a和b模m同余，记作 $a\equiv b \pmod{m}$ 。

例如， $13\equiv 1 \pmod{3}$ ，因为 $13\bmod 3=1$ ，而 $1\bmod 3=1$ ，即13和1除以3所得的余数相等。

在同余关系中，常见的定理有：

同余具有传递性：若 $a\equiv b\pmod{m}$ ， $b\equiv c\pmod{m}$ ，则有 $a\equiv c\pmod{m}$ 。同余具有对称性：若 $a\equiv b\pmod{m}$ ，则 $b\equiv a\pmod{m}$ 。同余具有反身性：对于任意的 $a$ 和 $m$ ，都有 $a\equiv a\pmod{m}$ 。同余可以进行加、减、乘法运算，即若 $a\equiv b\pmod{m}$ ， $c\equiv d\pmod{m}$ ，则有 $a+c\equiv b+d\pmod{m}$ ， $ac\equiv bd\pmod{m}$ 。

同余关系在数论中有着广泛的应用，例如模运算、同余方程（比如求解同余方程 $a\equiv b \pmod{m}$ ）、孙子定理等。

如有错误欢迎指正，谢谢！

参考： https://leetcode.cn/problems/power-of-four/

【本文地址】

python

python

今日新闻

推荐新闻