Make your Arduino/C++ code 8 times more efficient with a new BitArray Class!
BitArray started out in 2012 as an Arduino-only library. It has since
been refactored into a portable, dependency-free C++11 header that
drops into any C++ project — desktop or embedded, not just old 8-bit
microcontrollers — while keeping the exact same bit-packing algorithm
Joseph wrote for it. The library is on GitHub as
BitArray
(Apache-2.0). This is the original 2012 article that introduced it.
So, I remember when I first started coding for micro-controllers it was not long before I managed to run out of on chip memory with how inefficiently I had learned to program on the computer. In one for statement it is easy to cause a buffer overrun and make your chip do some seriously weird stuff.
Once I realized that was why my projects were crashing, I thought well I will solve my problems by storing registry values in a Boolean value. A Boolean is only a 1 or 0 so it should only take one bit of memory right? Wrong! I was quite disappointed to discover that a Boolean value still takes an entire byte of memory on the computer, and even worse, that the same policy carries over to the micro-controller world.
I know these days it seems efficiency is the last thing anyone cares about, but when you want to store large amounts of data in memory it may not be a big deal with 8 Gigabytes on a computer, but when you only have 1.5 K of ram the difference between being able to store less than 1000 or around 8000 points of usable data becomes quite significant. Sadly until recently I simply did not have the technical know-how to tackle the problem, so I simply avoided doing things that would require larger sums of memory on a micro-controller.
Recently I started helping out some students from Colorado State University Pueblo on a rover project, and what would you know we wanted to store Ultrasonic Mapping data in memory for navigation, but could only store 30 by 30 points of obstacle data. Sure for simple stuff that’s okay, but if you declare any variables after that your toast. That took me back to the drawing board, and brought me back to the idea I had had a couple years back of making a new data type that actually stored and handled data at the bit level.
What I managed to put together I am sure still has room for improvement (so please don’t hesitate to make any additions and let me know so we can keep the library as fast and efficient as possible), but what I was able to produce was a library that actually stores 8 bits of data, and allows individual bit manipulation and boolean like behavior without the the user having to perform bitwise manipulations. Whats better is that there is no additional overhead, an Array of 256 BitArrays takes just 256 Bytes in memory (which is 2048 Boolean values)!
That is to say 2048 Boolean values finally fits in 2048 Bits! The code works in C++ and in the Arduino environment, so if you are writing C code of any kind you should be able to use this class to make bit level manipulation easier, and make your memory usage more efficient.
CURRENT VERSION 1S0A — Library for the Arduino IDE available for download.
We put a lot of work into our hardware and software. Please share it if you know anyone that would benefit from our free libraries.
The code is available to download, but I present it here for those who are trying to understand it better, or do something similar in there code.
BitArray.h handles declaration of all class members, and implementation of a couple simple initialization routines:
/*####################################################################
FILE: BitArray.h
VERSION: 1S0A
PURPOSE: A new more efficient way to store boolean values at the bit level
LICENSE: GPL v3 (http://www.gnu.org/licenses/gpl.html)
DATASHEET: https://www.virtuabotix.com/resources.php?product=versalino
GET UPDATES: https://www.virtuabotix.com/resources.php?product=versalino
HISTORY:
Joseph Dattilo (Virtuabotix LLC) - Version 1S0A (04/13/12)
#######################################################################*/
#ifndef BITARRAY_H
#define BITARRAY_H
class BitArray;
typedef struct BitRef
{
bool value;
unsigned char position;
BitArray& parent;
void operator=(bool newValue);
void operator=(BitRef newValue);
bool operator!();
bool operator!=(bool myComp);
bool operator== (bool myComp);
bool operator!= (BitRef myComp);
bool operator== (BitRef myComp);
void setBit(bool newValue);
};
class BitArray
{
public:
BitRef operator[](unsigned char myPOS);
void operator=(unsigned char newValue);
BitArray(unsigned char myBITS) {setBits(myBITS);};
BitArray() {setBits(0);};
BitRef getBit(unsigned char myPOS);
void setBit(unsigned char position, bool newValue);
void setBits(unsigned char myBITS);
private:
unsigned char _myBITS;
};
#endif//BITARRAY_HBitArray.cpp handles the bitwise operations, and actual operator overloads that make the BitArray and BitRef data types behave correctly.
/*####################################################################
FILE: BitArray.cpp
VERSION: 1S0A
PURPOSE: A new more efficient way to store boolean values at the bit level
LICENSE: GPL v3 (http://www.gnu.org/licenses/gpl.html)
DATASHEET: https://www.virtuabotix.com/resources.php?product=versalino
GET UPDATES: https://www.virtuabotix.com/resources.php?product=versalino
HISTORY:
Joseph Dattilo (Virtuabotix LLC) - Version 1S0A (04/13/12)
#######################################################################*/
#ifndef BITARRAY_H
#include <stddef.h>
#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"
#else
#include "WProgram.h"
#include <pins_arduino.h>
#endif
#include "BitArray.h"
BitRef BitArray::operator[](unsigned char myPOS)
{
return getBit(myPOS);
}
BitRef BitArray::getBit(unsigned char myPOS)
{
BitRef myReturn = {(0x01 & (_myBITS >> myPOS)),myPOS,*this };
return myReturn;
}
void BitArray::setBit(unsigned char position, bool newValue)
{
if( getBit(position).value != newValue)
{
_myBITS = _myBITS ^ (0x80 >> (8-(position+1)));
}
}
void BitArray::operator=(unsigned char newValue)
{
setBits(newValue);
}
void BitArray::setBits(unsigned char myBITS)
{
_myBITS = myBITS;
}
void BitRef::setBit (bool newValue)
{
parent.setBit(position, newValue);
}
//--------------------------operators---------------------------------------
bool BitRef::operator!()
{
return !value;
}
void BitRef::operator = (bool newValue)
{
parent.setBit(position, newValue);
}
void BitRef::operator = (BitRef newValue)
{
parent.setBit(position, newValue.value);
}
bool BitRef::operator!=(bool myComp)
{
return value != myComp;
}
bool BitRef::operator== (bool myComp)
{
return value == myComp;
}
bool BitRef::operator!=(BitRef myComp)
{
return value != myComp.value;
}
bool BitRef::operator== (BitRef myComp)
{
return value == myComp.value;
}
//---------------------------------------------------------------------------
#endif // BITARRAY_H(The archived page’s code-embed widget did not render in the Wayback capture of this article — the two listings above are the canonical BitArray.h / BitArray.cpp source, version 1S0A, matching the version this article announces, recovered from the library source tree.)
I would love to hear if you have any suggested improvements, or if this code has helped you do something you couldn’t before. Happy coding!
Open source
BitArray is open source on GitHub as BitArray (Apache-2.0). The repo ships the original 1S0A algorithm above refactored into a single portable header (src/BitArray.h) with the Arduino-only dependency removed, so it drops into any C++11 project — desktop or embedded — with no build-system changes. It still works unmodified as an Arduino library: the original simpleExample and arrayOfBitArrays sketches are included as-is, alongside a new plain-C++ example that reproduces the same 8x memory saving outside the Arduino IDE.
Restored from the josephdattilo.com archive — original publish date April 14, 2012, preserved. Lightly cleaned up for the modern site; the words are period-correct. The library is released under Apache-2.0 with attribution to Joseph Dattilo.