Если у вас единички идут несколькими блоками, то можно сжимать столбцы, сохраняя только количества единиц и нулей в блоках. В случае, когда блоков совсем мало, вы и память сэкономите, и считать количество строк для набора столбцов можно будет быстро.
с памятью я согласен, у меня по сути около 5 регионов с единичками и хранить в таком формате для больших матриц - будет раз в 100 меньше памяти надо. А вот со скоростью - не уверен, вернее не понял Вашей мысли.
Если я перебираю номер столбца, то чтобы понять есть ли у меня единичка мне надо несколько сравнений сделать вместо одного. Причем если я в слово биты засовываю, то такие опериции ИЛИ идут за такт для 32 бит, а тут надо на каждую строку несколько сравнений. Или я все-таки Вашу мысль не уловил?