如何检查字节流中是否只有连续的1和0
How to check if there is only consecutive ones and zeros in bytestream
我想检查 int/long 是否仅由一组连续的 1 或零组成。例如 111100000
、1100000
但不是 101000
.
我有一个基本的实现如下:
def is_consecutive(val):
count = 0
while val %2 == 0:
count += 1
val = val >> 1
return (0xFFFFFFFF >> count ) & val
有没有更好的方法来实现这个?
如果速度是个问题,您可以只生成一个包含所有可接受值的字典,或者对它们进行硬编码。毕竟,我认为 32 位 int 只有 64 个可能值,而 64 位 long
有 128 个可能值
例如这是 4 位的所有 8 个可能值:
0000
0001
0011
0111
1111
1110
1100
1000
这是使用 groupby
的一种解决方案:
from itertools import groupby
def is_consecutive(seq):
if len([k for k,g in groupby(seq)]) > 2:
return False
return True
def is_consecutive_num(num):
return is_consecutive(str(bin(num))[2:])
print is_consecutive('111100000')
print is_consecutive('1100000')
print is_consecutive('101000')
print is_consecutive('01')
print is_consecutive('00111100000')
print is_consecutive('000000000')
print is_consecutive_num(400) # 110010000
print is_consecutive_num(96) # 1100000
print is_consecutive_num(40) # 101000
输出:
True
True
False
True
False
True
False
True
False
对于一个数字 n
,n | (n - 1)
将全部 当且仅当 它符合您描述的模式。
一个全为1的数x
比2的幂小1。你可以check for a power of two by ANDing it with itself minus one。或者换句话说,如果 x & (x + 1) == 0
.
,x
都是一位
def is_consecutive(n):
x = n | (n - 1)
return x & (x + 1) == 0
此测试程序根据正则表达式和 is_consecutive
检查数字,当两个测试都通过时打印星号。
#!/usr/bin/env python3
import re
def is_consecutive(n):
x = n | (n - 1)
return x & (x + 1) == 0
for n in range(64):
print('*' if re.fullmatch('0b1*0*', bin(n)) else ' ',
'*' if is_consecutive(n) else ' ',
n, bin(n))
实证测试证实这至少适用于 64。如您所见,星号完美匹配。
* * 0 0b0
* * 1 0b1
* * 2 0b10
* * 3 0b11
* * 4 0b100
5 0b101
* * 6 0b110
* * 7 0b111
* * 8 0b1000
9 0b1001
10 0b1010
11 0b1011
* * 12 0b1100
13 0b1101
* * 14 0b1110
* * 15 0b1111
* * 16 0b10000
17 0b10001
18 0b10010
19 0b10011
20 0b10100
21 0b10101
22 0b10110
23 0b10111
* * 24 0b11000
25 0b11001
26 0b11010
27 0b11011
* * 28 0b11100
29 0b11101
* * 30 0b11110
* * 31 0b11111
* * 32 0b100000
33 0b100001
34 0b100010
35 0b100011
36 0b100100
37 0b100101
38 0b100110
39 0b100111
40 0b101000
41 0b101001
42 0b101010
43 0b101011
44 0b101100
45 0b101101
46 0b101110
47 0b101111
* * 48 0b110000
49 0b110001
50 0b110010
51 0b110011
52 0b110100
53 0b110101
54 0b110110
55 0b110111
* * 56 0b111000
57 0b111001
58 0b111010
59 0b111011
* * 60 0b111100
61 0b111101
* * 62 0b111110
* * 63 0b111111
我想检查 int/long 是否仅由一组连续的 1 或零组成。例如 111100000
、1100000
但不是 101000
.
我有一个基本的实现如下:
def is_consecutive(val):
count = 0
while val %2 == 0:
count += 1
val = val >> 1
return (0xFFFFFFFF >> count ) & val
有没有更好的方法来实现这个?
如果速度是个问题,您可以只生成一个包含所有可接受值的字典,或者对它们进行硬编码。毕竟,我认为 32 位 int 只有 64 个可能值,而 64 位 long
有 128 个可能值例如这是 4 位的所有 8 个可能值:
0000
0001
0011
0111
1111
1110
1100
1000
这是使用 groupby
的一种解决方案:
from itertools import groupby
def is_consecutive(seq):
if len([k for k,g in groupby(seq)]) > 2:
return False
return True
def is_consecutive_num(num):
return is_consecutive(str(bin(num))[2:])
print is_consecutive('111100000')
print is_consecutive('1100000')
print is_consecutive('101000')
print is_consecutive('01')
print is_consecutive('00111100000')
print is_consecutive('000000000')
print is_consecutive_num(400) # 110010000
print is_consecutive_num(96) # 1100000
print is_consecutive_num(40) # 101000
输出:
True
True
False
True
False
True
False
True
False
对于一个数字 n
,n | (n - 1)
将全部 当且仅当 它符合您描述的模式。
一个全为1的数x
比2的幂小1。你可以check for a power of two by ANDing it with itself minus one。或者换句话说,如果 x & (x + 1) == 0
.
x
都是一位
def is_consecutive(n):
x = n | (n - 1)
return x & (x + 1) == 0
此测试程序根据正则表达式和 is_consecutive
检查数字,当两个测试都通过时打印星号。
#!/usr/bin/env python3
import re
def is_consecutive(n):
x = n | (n - 1)
return x & (x + 1) == 0
for n in range(64):
print('*' if re.fullmatch('0b1*0*', bin(n)) else ' ',
'*' if is_consecutive(n) else ' ',
n, bin(n))
实证测试证实这至少适用于 64。如您所见,星号完美匹配。
* * 0 0b0
* * 1 0b1
* * 2 0b10
* * 3 0b11
* * 4 0b100
5 0b101
* * 6 0b110
* * 7 0b111
* * 8 0b1000
9 0b1001
10 0b1010
11 0b1011
* * 12 0b1100
13 0b1101
* * 14 0b1110
* * 15 0b1111
* * 16 0b10000
17 0b10001
18 0b10010
19 0b10011
20 0b10100
21 0b10101
22 0b10110
23 0b10111
* * 24 0b11000
25 0b11001
26 0b11010
27 0b11011
* * 28 0b11100
29 0b11101
* * 30 0b11110
* * 31 0b11111
* * 32 0b100000
33 0b100001
34 0b100010
35 0b100011
36 0b100100
37 0b100101
38 0b100110
39 0b100111
40 0b101000
41 0b101001
42 0b101010
43 0b101011
44 0b101100
45 0b101101
46 0b101110
47 0b101111
* * 48 0b110000
49 0b110001
50 0b110010
51 0b110011
52 0b110100
53 0b110101
54 0b110110
55 0b110111
* * 56 0b111000
57 0b111001
58 0b111010
59 0b111011
* * 60 0b111100
61 0b111101
* * 62 0b111110
* * 63 0b111111