@zeit_geist There is a proof in the MoMD book on p.127 that you need to store all N bits if you want to count the number of 1's.