Skip to content

Instantly share code, notes, and snippets.

@cceasy
Created August 1, 2019 02:40
Show Gist options
  • Save cceasy/1fd0537df91b007f6afba38be734fdaf to your computer and use it in GitHub Desktop.
Save cceasy/1fd0537df91b007f6afba38be734fdaf to your computer and use it in GitHub Desktop.
# A bit array demo - written for Python 3.0
import array
def makeBitArray(bitSize, fill = 0):
intSize = bitSize >> 5 # number of 32 bit integers
if (bitSize & 31): # if bitSize != (32 * n) add
intSize += 1 # a record for stragglers
if fill == 1:
fill = 4294967295 # all bits set
else:
fill = 0 # all bits cleared
bitArray = array.array('I') # 'I' = unsigned 32-bit integer
bitArray.extend((fill,) * intSize)
return(bitArray)
# testBit() returns a nonzero result, 2**offset, if the bit at 'bit_num' is set to 1.
def testBit(array_name, bit_num):
record = bit_num >> 5
offset = bit_num & 31
mask = 1 << offset
return(array_name[record] & mask)
# setBit() returns an integer with the bit at 'bit_num' set to 1.
def setBit(array_name, bit_num):
record = bit_num >> 5
offset = bit_num & 31
mask = 1 << offset
array_name[record] |= mask
return(array_name[record])
# clearBit() returns an integer with the bit at 'bit_num' cleared.
def clearBit(array_name, bit_num):
record = bit_num >> 5
offset = bit_num & 31
mask = ~(1 << offset)
array_name[record] &= mask
return(array_name[record])
# toggleBit() returns an integer with the bit at 'bit_num' inverted, 0 -> 1 and 1 -> 0.
def toggleBit(array_name, bit_num):
record = bit_num >> 5
offset = bit_num & 31
mask = 1 << offset
array_name[record] ^= mask
return(array_name[record])
#* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
bits = 65536 # change these numbers to
ini = 1 # test the function
myArray = makeBitArray(bits, ini)
# array info: input bits; final length; excess bits; fill pattern
print(bits, len(myArray), (len(myArray) * 32) - bits, bin(myArray[0]))
# 0 and 1 are not prime, and not included in the Sieve of Eratosthenes:
bit = 0
clearBit(myArray, bit)
bit = 1
clearBit(myArray, bit)
for index in range(256): # range is to "square root" of limit
test = testBit(myArray, index)
if test:
zeroBit = index * index # prime squared is lowest multiple left
while zeroBit < 65536:
clearBit(myArray, zeroBit)
zeroBit += index
for index in range(65536):
test = testBit(myArray, index)
if test:
print(index)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment