如何获得大整数中最重要的位置？ [英] how to get the thighest bit position in big integers?
问题描述
我正在使用python为
加密应用程序开发一些概念验证代码。我的代码扩展了python的
本机bignum功能。
在许多加密应用程序中需要一个函数
''get_highest_bit_num''返回给定整数的最高
设置位的位置编号。例如：
get_highest_bit_num（（1<<< 159））== 159
get_highest_bit_num（（1<< 160）-1） == 159
get_highest_bit_num（（1<< 160））== 160
我通过以下方式实现：
def get_highest_bit_num（r）：
i = -1
而r 0：
r>> = 1
i = i + 1
返回i
这样可行，但这是一个非常不满意的解决方案，因为它是如此
慢。
我的第二次尝试是使用math.log函数：
导入数学
r =（1<<< 160） - 1
print highest_bit_num（r）＃打印出159
print math.floor（math.log（r， 2））＃打印出160.0
我们看到math.log只能作为最高位
位置的启发式算法。对于小r，例如r =（1 << 16）-1，来自
math.log（，2）的结果是正确的，对于大r，它不再是。
我向小组提出的问题：有没有人知道一种非hackish方式来确定
确定python中所需的位位置？我知道我的两个
想法
可以合并起来让事情有效。但是有没有*更好的方式，
这不是那种hackish吗？
欢呼，
mmg
mm******@gmx.de 写道：
我正在使用python开发一些概念验证
加密应用程序的代码。我的代码扩展了python的
本机bignum功能。
在许多加密应用程序中需要一个函数
''get_highest_bit_num''返回给定整数的最高
设置位的位置编号。例如：
get_highest_bit_num（（1<<< 159））== 159
get_highest_bit_num（（1<< 160）-1） == 159
get_highest_bit_num（（1<< 160））== 160
二进制搜索怎么样？
>>来自bisect import bisect
BITS = [1<< n n in range（1,1000）]＃在这里使用最大位数。
bisect（BITS，1<<< 159）
159
>> bisect（BITS，1<< 160-1）
159
< blockquote class =post_quotes>
>> bisect（BITS，1<< 160）
160
>>>
我不知道这是否更快。在搜索中使用的比较函数
（可能）很慢，但搜索是在（b）b的位数上的O（log n）而不是O（n），所以它值得一试。
如果你进行计时测试，请告诉我们结果。
加里赫伦
我通过以下方式实现：
def get_highest_bit_num（r）：
i = -1
而r 0：
r>> = 1
i = i + 1
返回i
这是有效的，但它是一个非常不令人满意的解决方案，因为它是如此美元b $ b慢。
我的第二次尝试是使用math.log函数：
导入数学
r =（1<<<< 160） - 1
打印highest_bit_num（r）＃打印159
打印math.floor（math.log（r，2））＃打印出160.0
我们看到math.log只能作为启发式算法最高位
pos银行足球比赛。对于小r，例如r =（1 << 16）-1，来自
math.log（，2）的结果是正确的，对于大r，它不再是。
我向小组提出的问题：有没有人知道一种非hackish方式来确定
确定python中所需的位位置？我知道我的两个
想法
可以合并起来让事情有效。但是有没有*更好的方式，
这不是那种hackish吗？
欢呼，
mmg
-
http：// mail.python.org/mailman/listinfo/python-list
mm ****** @ gmx.de 写道：
我对小组的提问：有没有人知道非hackish方式
确定python中所需的位位置？我知道我的两个
想法
可以合并起来让事情有效。但有没有*更好的方式，
这不是hackish？
如何使用值的十六进制表示法？
OFFSET = dict（（％x％i，int（c））i，c枚举（" 5433222211111111"））
def get_highest_bit_num（r）：
s ="％x"％r
返回len（s）* 4 - OFFSET [s [0]]
mm******@gmx.de 写道：
我正在使用python为
开发一些概念验证代码
加密应用程序。我的代码扩展了python的
本机bignum功能。
在许多加密应用程序中需要一个函数
''get_highest_bit_num''返回给定整数的最高
设置位的位置编号。例如：
get_highest_bit_num（（1<<< 159））== 159
get_highest_bit_num（（1<< 160）-1） == 159
get_highest_bit_num（（1<< 160））== 160
我通过以下方式实现：
def get_highest_bit_num（r）：
i = -1
而r 0：
r>> = 1
i = i + 1
返回i
这样可行，但这是一个非常不满意的解决方案，因为它是如此
慢。
一种方法是将r与2的连续较大幂进行比较，
从2 ** 0 == 1开始。鉴于你如果p = 2 **（n-1），则可以测试
是否为大n生成2 ** n更快，因为1 << n或p<< 1。一个
的优化是一次提高测试功率k而不是每次提高测试功率k，为实现调整k。然后在
区间n，n + k中进行二元搜索。我曾经读过longs存储15位成对的
字节。如果今天为真，那么k = 15可能是一个不错的选择，因为<< 15将
意味着对一对0字节进行处理。
我的第二次尝试是使用math.log函数：
导入数学
r =（1 << <160） - 1
print highest_bit_num（r）＃打印出159
打印math.floor（math.log（r，2））＃打印出160.0
我们看到math.log只能作为最高位
位置的启发式算法。对于小r，例如r =（1 << 16）-1，来自
math.log（，2）的结果是正确的，对于大r，它不再是。
我测试过并且楼层（log（2 ** n，2）== n表示n在范围内（400），所以你唯一的
担心答案是1太高。易于检查和修复
res = int（math.floor（math.log（r，2）））
if（1< res）r：res - = 1
这适用于相同范围内的2 ** n-1（所有测试均使用3.0rc1 ）。
我对小组的问题：有没有人知道一种非hackish方式来确定
确定python中所需的位位置？
如果你称标准方法是hackish，我不知道
能满足你;-)
Terry Jan Reedy
Hi,
I''m using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python''s
native bignum capabilities.
In many cryptographic applications there is the need for a function
''get_highest_bit_num'' that returns the position number of the highest
set bit of a given integer. For example:
get_highest_bit_num( (1 << 159)) == 159
get_highest_bit_num( (1 << 160) - 1) == 159
get_highest_bit_num( (1 << 160)) == 160
I implemented this the following way:
def get_highest_bit_num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i
This works, but it is a very unsatisfying solution, because it is so
slow.
My second try was using the math.log function:
import math
r = (1 << 160) - 1
print highest_bit_num(r) # prints out 159
print math.floor(math.log(r, 2)) # prints out 160.0
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn''t any more.
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn''t that hackish?
cheers,
mmg
mm******@gmx.de wrote:Hi,
I''m using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python''s
native bignum capabilities.
In many cryptographic applications there is the need for a function
''get_highest_bit_num'' that returns the position number of the highest
set bit of a given integer. For example:
get_highest_bit_num( (1 << 159)) == 159
get_highest_bit_num( (1 << 160) - 1) == 159
get_highest_bit_num( (1 << 160)) == 160
How about a binary search?
>>from bisect import bisect
BITS = [1<<n for n in range(1,1000)] # Use max number of bits here.
bisect(BITS, 1<<159)
159
>>bisect(BITS, 1<<160-1)
159
>>bisect(BITS, 1<<160)
160
>>>
I have no clue if this is faster or not. The comparison function used
in the search is (potentially) slow, but the search is O(log n) on the
number of bits rather than O(n), so its worth a test.
If you run timing test, let us know the results.
Gary Herron
I implemented this the following way:
def get_highest_bit_num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i
This works, but it is a very unsatisfying solution, because it is so
slow.
My second try was using the math.log function:
import math
r = (1 << 160) - 1
print highest_bit_num(r) # prints out 159
print math.floor(math.log(r, 2)) # prints out 160.0
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn''t any more.
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn''t that hackish?
cheers,
mmg
--
http://mail.python.org/mailman/listinfo/python-list
mm******@gmx.de wrote:
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn''t that hackish?
How about using the hex representation of the value?
OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433222211111111"))
def get_highest_bit_num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]
mm******@gmx.de wrote:Hi,
I''m using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python''s
native bignum capabilities.
In many cryptographic applications there is the need for a function
''get_highest_bit_num'' that returns the position number of the highest
set bit of a given integer. For example:
get_highest_bit_num( (1 << 159)) == 159
get_highest_bit_num( (1 << 160) - 1) == 159
get_highest_bit_num( (1 << 160)) == 160
I implemented this the following way:
def get_highest_bit_num(r):
i = -1
while r 0:
r >>= 1
i = i + 1
return i
This works, but it is a very unsatisfying solution, because it is so
slow.One alternative is to compare r against successive larger powers of 2,
starting with 2**0 == 1. Given that you have p=2**(n-1), you could test
whether generating 2**n for large n is faster as 1<<n or p<<1. A
refinement would be to raise the test power k at a time instead of 1 at
a time, tuning k for the implementation. Then do binary search in the
interval n, n+k. I once read that longs store 15 bits in pairs of
bytes. If true today, k = 15 might be a good choice since <<15 would
mean tacking on a pair of 0 bytes.
My second try was using the math.log function:
import math
r = (1 << 160) - 1
print highest_bit_num(r) # prints out 159
print math.floor(math.log(r, 2)) # prints out 160.0
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn''t any more.I tested and floor(log(2**n,2) == n for n in range(400), so your only
worry is that the answer is 1 too high. Easy to check and fix
res = int(math.floor(math.log(r, 2)))
if (1<<res) r: res -=1
This works for 2**n-1 over the same range (all tests with 3.0rc1).
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python?If you call the standard methods hackish, I have no idea what would
satisfy you ;-)
Terry Jan Reedy
这篇关于如何获得大整数中最重要的位置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
