Since memory is hardly a problem nowadays, I'd choose a representation which
- is easy to work with from a programmers point of view (readability)
- supports your algorithm
Using bit arrays will save space, but you'll end up with a lot of macros or function calls to separate the information over and over again. This is hard to read, hard to write and slow. (At least I guess your algorithm won't perform bit operations on your data)
If this were a database question, I'd say you definitely need first normal form as a minimum. Any higher level of normalization will reduce the effort of keeping data consistent.