Editing Bit array (section)

== Basic operations ==
Although most machines are not able to address individual bits in memory, nor have instructions to manipulate single bits, each bit in a word can be singled out and manipulated using [[bitwise operation]]s. In particular:

Use <code>OR</code> to set a bit to one:
    11101'''0'''10 
 OR 00000'''1'''00 
  = 11101'''1'''10
<code>AND</code> to set a bit to zero:
     111010'''1'''0
 AND 111111'''0'''1
   = 111010'''0'''0
<code>AND</code> to determine if a bit is set, by zero-testing:
        1110101'''0'''                111010'''1'''0
    AND 0000000'''1'''            AND 000000'''1'''0
      = 0000000'''0'''              = 000000'''1'''0
 (=0 ∴ bit isn't set)     (≠0 ∴ bit is set)

<code>XOR</code> to invert or toggle a bit:
     11101'''0'''10        11101'''1'''10
 XOR 00000'''1'''00    XOR 00000'''1'''00
   = 11101'''1'''10      = 11101'''0'''10

<code>NOT</code> to invert all bits:
 NOT 10110010 
   = 01001101

To obtain the [[Mask (computing)|bit mask]] needed for these operations, we can use a [[Bitwise operation#Bit shifts|bit shift]] operator to shift the number 1 to the left by the appropriate number of places, as well as [[bitwise negation]] if necessary.

Given two bit arrays of the same size representing sets, we can compute their [[union (set theory)|union]], [[intersection (set theory)|intersection]], and [[complement (set theory)|set-theoretic difference]] using ''n''/''w'' simple bit operations each (2''n''/''w'' for difference), as well as the [[Signed number representations#Ones' complement|complement]] of either:

 '''for''' i '''from''' 0 '''to''' n/w-1
     complement_a[i] := '''not''' a[i]
     union[i]        := a[i] '''or''' b[i]
     intersection[i] := a[i] '''and''' b[i]
     difference[i]   := a[i] '''and''' ('''not''' b[i])

If we wish to iterate through the bits of a bit array, we can do this efficiently using a doubly nested loop that loops through each word, one at a time. Only ''n''/''w'' memory accesses are required:

 '''for''' i '''from''' 0 to n/w-1
     index := 0    // if needed
     word := a[i]
     '''for''' b '''from''' 0 to w-1
         value := word '''and''' 1 ≠ 0
         word := word shift right 1
         // do something with value
         index := index + 1    // if needed

Both of these code samples exhibit ideal [[locality of reference]], which will subsequently receive large performance boost from a data cache. If a cache line is ''k'' words, only about ''n''/''wk'' cache misses will occur.