Software Orthodoxy: Bit Arrays

A bit array is an array that compactly stores bits. A bit may represent the values 0 or 1, or it can be viewed as representing the values False or True.

The C language has a somewhat loose interpretation of Boolean values, treating 0 as false and non-zero as true. The Ada programming language defines the Boolean type as the enumeration (False, True). Since that enumeration has only two values the Boolean type has only two position values. False is at position 0 and True is at position 1.

C array indexing is connected to memory addresses. The typical smallest memory addressable value is a byte, which is typically 8 bits. Indexing a bit array, where each bit within a string of bytes has its own index value requires some bit gymnastics.

The following C example is taken from https://www.sanfoundry.com/c-program-implement-bit-array/

Two functions are created.

The function toggle_bit toggles the bit at the index value specified by the function’s second parameter.

The function get_bit returns the numeric value of the bit at the index value specified by the function’s second value.

The output of the program is:

0: 1

1: 0

2: 1

3: 0

4: 1

5: 0

6: 1

7: 0

8: 1

9: 0

10: 1

11: 0

12: 1

13: 0

14: 1

15: 0

16: 1

17: 0

18: 1

19: 0

20: 1

21: 0

22: 1

23: 0

24: 1

25: 0

26: 1

27: 0

28: 1

29: 0

30: 1

31: 0

32: 1

33: 0

34: 1

35: 0

36: 1

37: 0

38: 1

39: 0

40: 1

41: 0

42: 1

43: 0

44: 1

45: 0

46: 1

47: 0

48: 1

49: 0

50: 1

51: 0

52: 1

53: 0

54: 1

55: 0

56: 0

57: 0

The Ada language allows the declaration of packed arrays of Boolean to represent each Boolean as a single bit.

Ada allows the programmer to use normal array index notation to access each element of a bit array.

The following Ada implementation of a bit array produces the same behavior as the C program except that the Ada program also displays the number of elements in the array and the number of bits occupied by an instance of the array.

An unconstrained array type named Bit_Array is declared. Each element of Bit_Array is a Boolean. Every instance of Bit_Array is packed, which causes the Boolean values to be represented by single bits.

Similar to the C program, the variable X is declared to be an instance of Bit_Array containing 58 elements. Whereas the C program uses a macro to create the array of bits, the Ada program uses normal Ada array declaration syntax. In C all the elements of the array are initialized to 0. In Ada all elements of the array are initialized to False.

The “while” loop in the Ada program toggles every other element in the array. The element indexed by the value 56 is then toggled again.

The “for” loop prints the Boolean position of each element of the array.

The output of the Ada program is

X contains 58 elements.

X occupies 64 bits