Bỏ đặt bit trong Python

Một số được đưa ra. Chúng ta phải xóa bit được đặt ngoài cùng bên phải của số. Tức là chúng ta phải lật số 1 ngoài cùng bên phải trong biểu diễn nhị phân của n

Giải pháp vấn đề

1. Hàm clear_rightmost_set_bit được xác định
2. Nó lấy một số n làm đối số và trả về n với bit được đặt ngoài cùng bên phải của nó đã bị xóa
3. Điều này được thực hiện bằng cách tính toán n & (n – 1) và trả về
4. (n – 1) bằng n với tất cả các số 0 liên tiếp ngoài cùng bên phải và số 1 ngoài cùng bên phải đầu tiên được lật
5. Do đó n & (n – 1) bằng n với số 1 ngoài cùng bên phải của nó bị xóa

Chương trình/Mã nguồn

Đây là mã nguồn của chương trình Python để xóa bit được đặt ngoài cùng bên phải của một số. Đầu ra chương trình được hiển thị dưới đây

Giả sử chúng ta có một số n và một giá trị khác k. Chúng ta phải kiểm tra xem bit thứ k trong n được đặt (1) hay không đặt (0). Giá trị của k được xem xét từ phía bên tay phải

Vì vậy, nếu đầu vào giống như n = 18 k = 2, thì đầu ra sẽ được Đặt ở dạng nhị phân của 18 là 10010 nên bit cuối cùng thứ hai là 1 (đặt)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nhiệt độ. = n sau khi dịch bit (k - 1) lần sang phải
• nếu temp AND 1 là 1, thì
• trả về "Bỏ đặt"

Chúng ta hãy xem triển khai sau đây để hiểu rõ hơn -

Mã ví dụ

Bản thử trực tiếp

def solve(n,k):
   temp = n >> (k - 1)
   if temp & 1:
      return "Set"
   return "Unset"

n = 18
k = 2
print(solve(n, k))

Đầu vào

18

đầu ra

Set

Cho một số dương và phạm vi của các bit. Nhiệm vụ của chúng tôi là đếm các bit chưa được đặt trong một phạm vi

Input : n = 50, starting address = 2, ending address = 5
Output : 2

Có '2' bit không được đặt trong phạm vi từ 2 đến 5

thuật toán

Step 1 : convert n into its binary using bin().
Step 2 : remove first two characters.
Step 3 : reverse string.
Step 4 : count all unset bit '0' starting from index l-1 to r, where r is exclusive.

Mã ví dụ

# Function to count unset bits in a range 
  
def countunsetbits(n,st,ed): 
   # convert n into it's binary 
   bi = bin(n) 
   # remove first two characters 
   bi = bi[2:] 
   # reverse string 
   bi = bi[-1::-1] 
   # count all unset bit '0' starting from index l-1 
   # to r, where r is exclusive 
   print (len([bi[i] for i in range(st-1,ed) if bi[i]=='0'])) 
  
# Driver program 
if __name__ == "__main__": 
   n=int(input("Enter The Positive Number ::>"))
   st=int(input("Enter Starting Position"))
   ed=int(input("Enter Ending Position"))
   countunsetbits(n,st,ed) 

đầu ra

Enter The Positive Number ::> 50
Enter Starting Position2
Enter Ending Position5
2

Không sử dụng các lựa chọn thay thế sử dụng eval. eval sẽ thực thi mã được truyền cho nó và do đó có thể ảnh hưởng đến tính bảo mật của chương trình của bạn

Số nguyên thành chuỗi Bin

Python 3 hỗ trợ chữ nhị phân (e. g. 0b10011000) và có hàm bin(). Đối với các phiên bản cũ hơn

   1 >>> def bin(a):
   2         s=''
   3         t={'0':'000','1':'001','2':'010','3':'011',
   4            '4':'100','5':'101','6':'110','7':'111'}
   5         for c in oct(a)[1:]:
   6                 s+=t[c]
   7         return s

hoặc tốt hơn

________số 8_______

Số nguyên trong Python

Từ trang "Tham khảo ngôn ngữ Python" trên Mô hình dữ liệu

"Số nguyên (int) Những số này biểu thị các số trong phạm vi không giới hạn, chỉ tùy thuộc vào bộ nhớ (ảo) khả dụng. Với mục đích của các phép toán dịch chuyển và mặt nạ, một biểu diễn nhị phân được giả định và các số âm được biểu diễn dưới dạng một biến thể của phần bù 2, điều này tạo ảo giác về một chuỗi vô hạn các bit dấu kéo dài sang trái. "

Trước Python 3. 1, không có cách nào dễ dàng để xác định cách Python đại diện cho một số nguyên cụ thể bên trong, tôi. e. bao nhiêu bit đã được sử dụng. Trăn 3. 1 thêm phương thức bit_length() vào kiểu int thực hiện chính xác điều đó

Trừ khi bạn biết mình đang làm việc với các số nhỏ hơn một độ dài nhất định, chẳng hạn như các số từ mảng số nguyên, phép dịch chuyển, phép quay, v.v. có thể cho kết quả bất ngờ

Số lượng bit cao nhất được đặt là lũy thừa cao nhất của 2 nhỏ hơn hoặc bằng số nguyên đầu vào. Điều này giống như số mũ của biểu diễn dấu phẩy động của số nguyên và còn được gọi là "cơ sở nhật ký số nguyên 2" của nó. (tham khảo. 1)

Trong các phiên bản trước 3. 1, cách dễ nhất để xác định tập hợp bit cao nhất là*

* Có một cuộc thảo luận dài về chủ đề này và tại sao phương pháp này không tốt, trong "Số 3439" tại Python. tổ chức. http. // lỗi. con trăn. org/issue3439 Cuộc thảo luận này đã dẫn đến việc bổ sung bit_length() trong Python 3. 1

   1 import math
   2 
   3 hiBit = math.floor(math.log(int_type, 2))

Một đầu vào nhỏ hơn hoặc bằng 0 dẫn đến lỗi "ValueError. lỗi miền toán học"

Phần "Tìm log số nguyên cơ số 2 của một số nguyên" trong "Bit Twiddling Hacks"(tham khảo. 1) trang web bao gồm một số phương pháp để xác định giá trị này cho các số nguyên có độ lớn đã biết, có lẽ là khi không có sẵn bộ đồng xử lý toán học. Phương pháp duy nhất thường áp dụng cho các số nguyên Python có độ lớn không xác định là "cách rõ ràng" để đếm số lượng thao tác dịch chuyển bit cần thiết để giảm đầu vào thành 0

Độ dài bit của số nguyên Python

bitLen() đếm độ dài bit thực của một số nguyên Python, nghĩa là số lượng bit khác 0 cao nhất cộng với 1. Số không, không có bit khác không, trả về 0. Như được mong đợi từ câu trích dẫn ở trên về "ảo giác về một chuỗi vô hạn các bit dấu kéo dài sang trái", một số âm sẽ ném máy tính vào một vòng lặp vô hạn

Hàm có thể trả về bất kỳ kết quả nào có độ dài bằng số nguyên lớn nhất mà bộ nhớ máy tính của bạn có thể chứa

Phương pháp sử dụng mô-đun toán học nhanh hơn nhiều, đặc biệt là trên các số lớn có hàng trăm chữ số thập phân

bitLenCount()

Trong cách sử dụng phổ biến, "số bit" của một số nguyên là số bit được đặt (1), không phải độ dài bit của số nguyên được mô tả ở trên. bitLen() có thể được sửa đổi để cung cấp số lượng bit đã đặt trong số nguyên. Có các phương pháp nhanh hơn để có được số lượng dưới đây

   1 def bitLenCount(int_type):
   2     length = 0
   3     count = 0
   4     while (int_type):
   5         count += (int_type & 1)
   6         length += 1
   7         int_type >>= 1
   8     return(length, count)

Các phép toán trên số nguyên có độ lớn chưa biết

Một số thủ tục không cần biết độ lớn của một số nguyên để cho kết quả có ý nghĩa

bitCount()

Quy trình và thông tin bên dưới được tìm thấy trong "Bit Twiddling Hacks"(tham khảo. 1)

• - - - - - - - - - - - - - - - - - - - - - - -

Bộ đếm số bit, cách của Brian Kernighan*

   1 unsigned int v;          // count the number of bits set in v
   2 unsigned int c;          // c accumulates the total bits set in v
   3 for (c = 0; v; c++)
   4 {   v &= v - 1;  }       //clear the least significant bit set

Phương pháp này trải qua nhiều lần lặp lại khi có các bit được đặt. Vì vậy, nếu chúng ta có một từ 32 bit chỉ có bit cao được đặt, thì nó sẽ chỉ đi một lần qua vòng lặp

* Ngôn ngữ lập trình C 2nd Ed. , Kernighan & Ritchie, 1988

Don Knuth chỉ ra rằng phương pháp này đã được xuất bản bởi Peter Wegner trong CACM 3 (1960), 322. Cũng được phát hiện độc lập bởi Derrick Lehmer và xuất bản năm 1964 trong một cuốn sách do Beckenbach biên tập

• - - - - - - - - - - - - - - - - - - - - - - -

Kernighan và Knuth, những chứng thực mạnh mẽ

Điều này hoạt động vì mỗi phép trừ "mượn" từ 1 bit thấp nhất. Ví dụ

Đây là một kỹ thuật tuyệt vời cho Python, vì không cần xác định trước kích thước của số nguyên

   1 >>> print "0x%x" % int('11111111', 2)
   2 0xff
   3 >>> print "0x%x" % int('0110110110', 2)
   4 0x1b6
   5 >>> print "0x%x" % int('0010101110101100111010101101010111110101010101', 2)
   6 0xaeb3ab57d55

tính chẵn lẻ()

Từ "Bit Twiddling Hacks"

Mã gần giống với bitCount(), ở trên, tính toán tính chẵn lẻ của một số nguyên, trả về 0 nếu có số bit được đặt là chẵn và -1 nếu có số lẻ. Trên thực tế, việc đếm các bit và kiểm tra xem kết quả có phải là số lẻ hay không với bitcount & 1 có cùng tốc độ với hàm chẵn lẻ

   1 >>> print "0x%x" % int('11111111', 2)
   2 0xff
   3 >>> print "0x%x" % int('0110110110', 2)
   4 0x1b6
   5 >>> print "0x%x" % int('0010101110101100111010101101010111110101010101', 2)
   6 0xaeb3ab57d55

bộ thấp nhất()

Để xác định số bit của bit thấp nhất được đặt trong một số nguyên, trong ký hiệu bù hai i & -i bỏ qua tất cả trừ bit được đặt thấp nhất. Quá trình bitLen() sau đó xác định vị trí của nó. Rõ ràng, các số âm trả về kết quả tương tự như đối diện của chúng. Trong phiên bản này, đầu vào là 0 trả về -1, thực tế là một điều kiện lỗi

   1 >>> print "0x%x" % int('11111111', 2)
   2 0xff
   3 >>> print "0x%x" % int('0110110110', 2)
   4 0x1b6
   5 >>> print "0x%x" % int('0010101110101100111010101101010111110101010101', 2)
   6 0xaeb3ab57d55

bit đơn

Các hoạt động bit đơn thông thường sẽ hoạt động trên bất kỳ số nguyên Python nào. Người lập trình phải đảm bảo rằng giá trị của 'offset' có ý nghĩa trong ngữ cảnh của chương trình

Nếu bạn cần giải thích các bit riêng lẻ trong một số dữ liệu, e. g. luồng byte trong giao thức truyền thông, bạn có thể sử dụng mô-đun ctypes

Làm cách nào để sử dụng bitwise không có trong Python?

Thao tác bit trong Python là gì?

Bitmask trong Python là gì?