Use binary bits to represent integers, such as 1 in the ninth position of a binary bit to represent the integer 9.

Binary: 10 0000 0000 represents decimal: 9

The first element of the array can represent 1 to 32 bytes, and the second element can represent 33 to 64… And so on.

First define the variables to use. Suppose we need to store integers up to 100 million:

letBits = 32 // Int Occupies 4 bytes, a total of 32 bitslet shift= 5 // 32 is 2 to the fifth power, which means the offset is 5let mask = 31 
let n = 10_000_000
var nums = Array(repeating: 0, count: 1 + n / bits)
Copy the code

Add function

Now let’s look at the add function. This function requires the following three steps:

  • 1) Calculate the index of the current integer in the array
  • 2) Compute 2 to the power of the current integer
  • 3) Store the value obtained in step 2 or the value stored by the current index in the array above into the array

Let’s elaborate on the above three steps:

Calculates the index of the current integer in the array

Take the decimal integer 45 as an example. Here is the index code for calculating 45:

let index = 45 >> shift// Equivalent to 45/32Copy the code

The above code calculates that the index of 45 is 1, that is, index = 1. After the index is computed, the specific value stored in that index is computed.

Compute 2 to the power of the current integer

Take 45 for example:

letPower = 1 << (45&mask) // equivalent to 2 to the 45th powerCopy the code

Store the result to the array with the value obtained in step 2 or the value stored by the current index in the array above

let oldValue = nums[index]
let newValue = oldValue | power
nums[index] = newValue
Copy the code

The or method is used because it does not affect the value stored last time, because the value stored last time already has the corresponding position 1.

The complete add-on function:

func set(_ newElement: Int) {
    let index = newElement >> shift
    let power = 1 << (newElement & mask)
    let oldValue = nums[index]
    let newValue = oldValue | power
    nums[index] = newValue
}
Copy the code

Remove the function

There are three steps to remove the function:

  • 1) Calculate index (ibid.)
  • 2) Compute 2 to the power of the current integer and take the inverse
  • 3) Add the value obtained in step 2 to the value stored by the current index in the array above, and store the result into the array

Compute 2 to the power of the current integer, inverse

let power = 1 << (element & mask)
let negation = ~power
let oldValue = nums[index]
let newValue = oldValue & negation
nums[index] = newValue
Copy the code

The complete removal function:

func remove(_ element: Int) {
    let index = element >> shift
    let power = 1 << (element & mask)
    let negation = ~power
    let oldValue = nums[index]
    let newValue = oldValue & negation
    nums[index] = newValue
}
Copy the code

Access to functions

There are three steps to get the function:

  • 1) Calculate index (ibid.)
  • 2) Compute 2 to the power of the current integer (ibid.)
  • 3) Add the value obtained in step 2 to the value stored by the current index in the array above, and return the result

Complete code:

func get(_ element: Int) -> Int {
    let index = element >> shift
    let value = 1 << (element & mask)
    return nums[index] & value
}
Copy the code

The test code

set(30)
print(NUMS [0]) // 2 ^ 30 1073741824print(get(30)) // 1073741824
remove(30)
print(get(30)) // 0
Copy the code

Easy-to-read version of the complete code:

func set(_ newElement: Int) {
    let index = newElement >> shift
    let power = 1 << (newElement & mask)
    let oldValue = nums[index]
    let newValue = oldValue | power
    nums[index] = newValue
}

func remove(_ element: Int) {
    let index = element >> shift
    let power = 1 << (element & mask)
    let negation = ~power
    let oldValue = nums[index]
    let newValue = oldValue & negation
    nums[index] = newValue
}

func get(_ element: Int) -> Int {
    let index = element >> shift
    let value = 1 << (element & mask)
    return nums[index] & value
}
Copy the code

The following version of the code is a simple version (I find it difficult to read) :

func set(_ newElement: Int) {
    let index = newElement >> shift
    let curNum = nums[index]
    nums[index] = curNum | (1 << (newElement & mask))
}

func remove(_ element: Int) {
    let index = element >> shift
    nums[index] &= ~(1 << (element & mask))
}

func get(_ element: Int) -> Int {
    let index = element >> shift
    return nums[index] & (1 << (element & mask))
}
Copy the code