Tìm số mũ của n = 2 ** x bằng cách sử dụng các phép toán bit [logarit trong cơ sở 2 của n]

Question

Có cách nào đơn giản để trích xuất số mũ từ lũy thừa 2 bằng cách sử dụng các thao tác bitwise không?

EDIT: Mặc dù câu hỏi ban đầu về hoạt động Bitwise, thread là một đọc tốt còn nếu bạn đang tự hỏi "? Cách nhanh nhất để tìm X đã cho là gì Y = 2 X bằng Python" * *

tôi hiện đang cố gắng để tối ưu hóa một thói quen (Rabin-Miller primality test) làm giảm một số chẵn N trong các hình thức 2**s * d. Tôi có thể lấy một phần 2**s bởi:

two_power_s = N & -N 

nhưng tôi không thể tìm thấy một cách để chỉ trích "s" với một thao tác trên bit. Cách giải quyết Tôi hiện đang thử nghiệm mà không cần quá nhiều sự hài lòng (tất cả chúng đều khá nhiều chậm) là:

• sử dụng chức năng logarit
• thao tác biểu diễn nhị phân của 2 ** s (tức là đếm zero trailing)
• looping trên một bộ phận của 2 cho đến khi kết quả là 1

Tôi đang sử dụng python, nhưng câu trả lời cho câu hỏi này nên là ngôn ngữ bất khả tri, tôi cho là vậy.

Answer 1

Câu trả lời ngắn

Theo như trăn là có liên quan:

• Các phương pháp nhanh nhất của tất cả các để tìm số mũ của 2 ** x là bằng cách nhìn lên trong một cuốn từ điển mà băm là quyền hạn của 2 (xem "hashlookup" trong code)
• các nhanh nhất phương pháp Bitwise là một gọi là "unrolled_bitwise ".
• Cả hai phương pháp trước đây đều có giới hạn trên được xác định rõ ràng (nhưng có thể mở rộng). Phương thức nhanh nhất mà không có giới hạn trên được mã hóa cứng (có quy mô lên đến mức python có thể xử lý số) là "log_e".

ghi chú sơ bộ

1. Tất cả các phép đo tốc độ dưới đây đã được thu được thông qua timeit.Timer.repeat(testn, cycles) nơi testn được thành lập đến 3 và cycles được tự động điều chỉnh theo kịch bản để có được thời gian trong khoảng giây (lưu ý : đã xảy ra lỗi trong cơ chế điều chỉnh tự động này đã được khắc phục vào ngày 18/02/2010).
2. Không phải tất cả các phương pháp có thể mở rộng, đây là lý do tại sao tôi đã không kiểm tra tất cả các chức năng cho các cường quốc khác nhau của 2
3. tôi không quản lý để có được một số phương pháp được đề nghị làm việc (hàm trả về một sai lầm kết quả).Tôi chưa có câu hỏi để thực hiện một phiên gỡ lỗi từng bước: Tôi đã bao gồm mã (nhận xét) chỉ trong trường hợp ai đó phát hiện lỗi do kiểm tra (hoặc muốn tự thực hiện gỡ lỗi)

Kết quả

func (2 5) **

hashlookup:   0.13s  100% 
lookup:    0.15s  109% 
stringcount:   0.29s  220% 
unrolled_bitwise: 0.36s  272% 
log_e:    0.60s  450% 
bitcounter:   0.64s  479% 
log_2:    0.69s  515% 
ilog:    0.81s  609% 
bitwise:    1.10s  821% 
olgn:    1.42s 1065% 

func (2 31) **

hashlookup:   0.11s  100% 
unrolled_bitwise: 0.26s  229% 
log_e:    0.30s  268% 
stringcount:   0.30s  270% 
log_2:    0.34s  301% 
ilog:    0.41s  363% 
bitwise:    0.87s  778% 
olgn:    1.02s  912% 
bitcounter:   1.42s 1264% 

func (2 128) **

hashlookup:  0.01s  100% 
stringcount: 0.03s  264% 
log_e:   0.04s  315% 
log_2:   0.04s  383% 
olgn:   0.18s 1585% 
bitcounter:  1.41s 12393% 

func (2 1024) **

log_e:   0.00s  100% 
log_2:   0.01s  118% 
stringcount: 0.02s  354% 
olgn:   0.03s  707% 
bitcounter:  1.73s 37695% 

Mã

import math, sys 

def stringcount(v): 
    """mac"""  
    return len(bin(v)) - 3 

def log_2(v): 
    """mac"""  
    return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999 

def log_e(v): 
    """bp on mac"""  
    return int(round(math.log(v)/0.69314718055994529, 0)) # 0.69 == log(2) 

def bitcounter(v): 
    """John Y on mac""" 
    r = 0 
    while v > 1 : 
     v >>= 1 
     r += 1 
    return r 

def olgn(n) : 
    """outis""" 
    if n < 1: 
     return -1 
    low = 0 
    high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but... 
    while True: 
     mid = (low+high)//2 
     i = n >> mid 
     if i == 1: 
      return mid 
     if i == 0: 
      high = mid-1 
     else: 
      low = mid+1 

def hashlookup(v): 
    """mac on brone -- limit: v < 2**131""" 
# def prepareTable(max_log2=130) : 
#  hash_table = {} 
#  for p in range(1, max_log2) : 
#   hash_table[2**p] = p 
#  return hash_table 

    global hash_table 
    return hash_table[v] 

def lookup(v): 
    """brone -- limit: v < 2**11""" 
# def prepareTable(max_log2=10) : 
#  log2s_table=[0]*((1<<max_log2)+1) 
#  for i in range(max_log2+1): 
#   log2s_table[1<<i]=i 
#  return tuple(log2s_table) 

    global log2s_table 
    return log2s_table[v] 

def bitwise(v): 
    """Mark Byers -- limit: v < 2**32""" 
    b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000) 
    S = (1, 2, 4, 8, 16) 
    r = 0 
    for i in range(4, -1, -1) : 
     if (v & b[i]) : 
      v >>= S[i]; 
      r |= S[i]; 
    return r 

def unrolled_bitwise(v): 
    """x4u on Mark Byers -- limit: v < 2**33""" 
    r = 0; 
    if v > 0xffff : 
     v >>= 16 
     r = 16; 
    if v > 0x00ff : 
     v >>= 8 
     r += 8; 
    if v > 0x000f : 
     v >>= 4 
     r += 4; 
    if v > 0x0003 : 
     v >>= 2 
     r += 2; 
    return r + (v >> 1) 

def ilog(v): 
    """Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32""" 
    ret = 1 
    m = (not not v & 0xFFFF0000) << 4; 
    v >>= m; 
    ret |= m; 
    m = (not not v & 0xFF00) << 3; 
    v >>= m; 
    ret |= m; 
    m = (not not v & 0xF0) << 2; 
    v >>= m; 
    ret |= m; 
    m = (not not v & 0xC) << 1; 
    v >>= m; 
    ret |= m; 
    ret += (not not v & 0x2); 
    return ret - 1; 


# following table is equal to "return hashlookup.prepareTable()" 
hash_table = {...} # numbers have been cut out to avoid cluttering the post 

# following table is equal to "return lookup.prepareTable()" - cached for speed 
log2s_table = (...) # numbers have been cut out to avoid cluttering the post 

Answer 2

Có một trang có rất nhiều loại mẹo và thủ thuật này. Nó được viết cho C, nhưng nhiều người trong số họ nên làm việc trong Python quá (mặc dù hiệu suất rõ ràng sẽ khác nhau). Bit bạn muốn là here và trở đi.

Bạn có thể thử this ví dụ:

register unsigned int r = 0; // result of log2(v) will go here 
for (i = 4; i >= 0; i--) // unroll for speed... 
{ 
    if (v & b[i]) 
    { 
    v >>= S[i]; 
    r |= S[i]; 
    } 
} 

Điều đó có vẻ như nó có thể được chuyển đổi sang Python khá dễ dàng.

Answer 3

Bạn có thể làm điều đó trong thời gian O (lg s) cho các số nguyên chiều dài tùy ý bằng cách sử dụng một binsearch.

import sys 
def floorlg(n): 
    if n < 1: 
     return -1 
    low=0 
    high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but... 
    while True: 
     mid = (low+high)//2 
     i = n >> mid 
     if i == 1: 
      return mid 
     if i == 0: 
      high = mid-1 
     else: 
      low = mid+1 

Đối với số nguyên kích thước cố định, bảng tra cứu phải là giải pháp nhanh nhất và có thể là tổng thể tốt nhất.

Answer 4

"ngôn ngữ bất khả tri" và đáng lo ngại về hiệu suất là khá nhiều khái niệm không tương thích.

Hầu hết các bộ xử lý hiện đại đều có lệnh CLZ, "đếm số 0 đứng đầu". Trong GCC bạn có thể nhận được nó với __builtin_clz (x) (cũng tạo ra hợp lý, nếu không phải là mã nhanh nhất, cho các mục tiêu thiếu clz). Lưu ý rằng CLZ này không được xác định cho số không, vì vậy bạn sẽ cần một nhánh phụ để nắm bắt trường hợp đó nếu nó quan trọng trong ứng dụng của bạn.

Trong CELT (http://celt-codec.org) CLZ không có nhánh mà chúng tôi sử dụng cho người khiếu nại thiếu một CLZ được viết bởi Timothy B.Terriberry:

int ilog(uint32 _v){ 
    int ret; 
    int m; 
    ret=!!_v; 
    m=!!(_v&0xFFFF0000)<<4; 
    _v>>=m; 
    ret|=m; 
    m=!!(_v&0xFF00)<<3; 
    _v>>=m; 
    ret|=m; 
    m=!!(_v&0xF0)<<2; 
    _v>>=m; 
    ret|=m; 
    m=!!(_v&0xC)<<1; 
    _v>>=m; 
    ret|=m; 
    ret+=!!(_v&0x2); 
    return ret; 
} 

(Các ý kiến ​​chỉ ra rằng điều này đã được tìm thấy là nhanh hơn so với một phiên bản phân nhánh và một phiên bản bảng tra cứu có trụ sở)

Nhưng nếu hiệu suất là quan trọng có lẽ bạn không nên thực hiện phần này mã của bạn trong python.

Answer 5

nó có vẻ như phạm vi là biết . Giả sử nó đi lên tới 1 < < 20, chỉ để làm cho nó thú vị hơn:

max_log2=20 

Vì vậy, làm cho một danh sách đó (có hiệu lực) bản đồ một số nguyên để cơ sở 2 logarit của nó. Sau đây sẽ thực hiện thủ thuật:

log2s_table=[0]*((1<<max_log2)+1) 
for i in range(max_log2+1): 
    log2s_table[1<<i]=i 

(Điều này không làm bất cứ điều gì hữu ích cho các số không có quyền hạn của hai người); sửa chữa mặc dù đó)

chức năng để có được logarit là rất đơn giản, và có thể dễ dàng được inlined:.

def table(v): 
    return log2s_table[v] 

tôi không thể đảm bảo rằng mã thử nghiệm tôi đã viết là chính xác giống như một trong những được sử dụng để có được thời gian ví dụ, nhưng điều này là khá nhanh hơn so với stringcount mã:

stringcount: 0.43 s. 
table: 0.16 s. 

Vì tất cả các giá trị trong bảng là ít hơn 256, tôi tự hỏi liệu sử dụng một chuỗi thay vì một danh sách sẽ được nhanh hơn, hoặc có thể một array.array byte, nhưng không có con xúc xắc:

string: 0.25 s. 
arr: 0.21 s. 

Sử dụng một dict để làm tra cứu là một khả năng khác, lợi dụng con đường duy nhất, quyền hạn của hai đang được kiểm tra:

log2s_map=dict([(1<<x,x) for x in range(max_log2+1)]) 

def map(v): 
    return log2s_map[v] 

Kết quả cho điều này là không tốt, mặc dù:

map: 0.20 s. 

Và chỉ để cho vui người ta cũng có thể sử dụng phương pháp hex trên các đối tượng phao để có được một chuỗi bao gồm (như phần cuối cùng của nó) cơ sở 2 số mũ của con số.Đây là một chút chậm chạp trong việc trích xuất nói chung, nhưng nếu số mũ chỉ bao giờ sẽ trở thành một chữ số nó có thể được thực hiện thẳng thắn đủ:

def floathex(v): 
    return ord(float(v).hex()[-1])-48 

này là hoàn toàn cho dù giá trị giải trí như nó đã được uncompetetive - mặc dù , đáng ngạc nhiên, vẫn nhanh hơn cách tiếp cận bitwise.

Vì vậy, có vẻ như sử dụng danh sách là cách để thực hiện.

(Cách tiếp cận này sẽ không quy mô vô thời hạn do bộ nhớ bị giới hạn, nhưng bù lại tốc độ thực thi sẽ không phụ thuộc vào max_log2 hoặc giá trị đầu vào theo bất kỳ cách nào bạn sẽ thấy khi chạy python Về mức tiêu thụ bộ nhớ, nếu tôi nhớ chính xác nội dung python, bảng sẽ chiếm khoảng (1<<max_log2)*4 byte, vì nội dung là tất cả các số nguyên nhỏ mà trình thông dịch sẽ tự động thực hiện. SO, khi max_log2 là 20, tức là khoảng 4MB.)

Answer 6

Đây thực sự là nhận xét về kiểm tra hiệu suất được đăng bởi mac. Tôi đăng câu trả lời này để có định dạng mã thích hợp và thụt lề

mac, bạn có thể thử triển khai chưa được kiểm tra của biteach do Mark Byers đề xuất không? Có lẽ nó chỉ là truy cập mảng làm chậm nó xuống. Về lý thuyết, phương pháp này nên nhanh hơn các phương pháp khác.

Nó sẽ trông giống như thế này, mặc dù tôi không chắc liệu định dạng có phù hợp với python hay không nhưng tôi đoán bạn có thể thấy nó được cho là gì.

def bitwise(v): 
    r = 0; 
    if(v > 0xffff) : v >>= 16; r = 16; 
    if(v > 0x00ff) : v >>= 8; r += 8; 
    if(v > 0x000f) : v >>= 4; r += 4; 
    if(v > 0x0003) : v >>= 2; r += 2; 
    return r + (v >> 1); 

Nếu cổ phiếu trăn java của thiếu nguyên unsingned nó sẽ cần phải được một cái gì đó như thế này:

def bitwise(v): 
    r = 0; 
    if(v & 0xffff0000) : v >>>= 16; r = 16; 
    if(v > 0x00ff) : v >>= 8; r += 8; 
    if(v > 0x000f) : v >>= 4; r += 4; 
    if(v > 0x0003) : v >>= 2; r += 2; 
    return r + (v >> 1);