Logo

Programming-Idioms

  • Pascal
  • Lua

Idiom #68 Create a bitset

Create an object x to store n bits (n being potentially large).

import "math/big"
var x *big.Int = new(big.Int)

big.Int type makes a decent bitset.
It grows automatically when needed.
x := make([]bool, n)

This makes a simple fixed-size bitset.
It uses more bits in memory than the useful size n.
x := make([]uint64, (n+63)/64)

This compact bitset requires some extra logic to implement get, set, clear (see demo).
procedure Task;
var
  x: Set Of Byte;
begin
  x:= [2,4,8,16,32,64,256];  
end;

when the set contains less than 256 elements the built-in Set Of construct can be used.
uses classes;
procedure task;
var 
  x: TBits;
  n: integer;
begin 
  n := $FFF;
  x := TBits.Create(n);
end;

when the set contains more than 256 elements the class TBits must be used
#include <bitset>
std::bitset<n> x;
New implementation...
< > ⌨
programming-idioms.org 
var x *big.Int = new(big.Int)
x := make([]bool, n)
x := make([]uint64, (n+63)/64)
procedure Task;
var
  x: Set Of Byte;
begin
  x:= [2,4,8,16,32,64,256];  
end;
procedure task;
var 
  x: TBits;
  n: integer;
begin 
  n := $FFF;
  x := TBits.Create(n);
end;
std::bitset<n> x;
std::vector<bool> x(n, 0);
new BitArray(n);
BitArray x;
x.length = n;
final x = FixedBitArray(n);
x :: Integer
x = sum [bit i | i <- [1..n], wannaset i]

let x = new Buffer (Math.ceil (n / 8))
BitSet x = new BitSet(n);
(let ((x (make-array n :element-type 'bit))))
$x = new BitSet($n);
vec($x, $n, 1) = 0;
x = bytearray(int(math.ceil(n / 8.0)))
class BitSet:
    def __init__(self, n):
        self.a = [False] * n
    def __getitem__(self, i):
        return self.a[i]
    def __setitem__(self, k, v):
        self.a[k] = v
    def __str__(self):
        s = ('01'[x] for x in self.a)
        return ''.join(s)
x = BitSet(n)
x = 0
let mut x = vec![false; n];