общий вопрос по программированию — расчитать индекс массива

>по идее, всю информацию о том, в каких ячейках информация, а в каких мусор можно представить ввиде двоичного числа (111100011111...N1)

А какой размер массива? Число не переполнится?

Э... так делать не надо. При каждом переносе R надо делать дефрагментацию A_i. Т.е. для каждого A_i мы храним число актуальных элементов N_i, если из A_i нужно убрать элемент и этот элемент не последний, пишем на его место последний элемент и декрементируем N_i. Новый элемент добавляется в конец, N_i инкрементируется. Тогда все актуальные элементы всегда лежат вначале A_i и никаких проблем;-)

«свободных, не несущих информациюб, ячеек заведомо больше, чем значащих» Тогда есть надежда что такой фрагмент кода

	if( b == 0 )
		cout<<"all zeroes"<<endl;
	else if( b == -1 )
		cout<<"all ones"<<endl;
	else if( (b & (b-1) ) == 0)
		cout<<"sigle one on "<<__builtin_clz(b)<<endl;
	else while( b ){
		int pos= __builtin_clz(b);
		cout<<pos<<endl;
		b ^= 1<<(31-pos); 
		}

эээ.. а если подохли не один, а несколько элементов?

что то похоже надо снова к вам подъехать, проконсультироваться.

Они ж не сразу, а по одному дохнут (типа в цикле). Кто сдох - на его место последнего.

Хотите - приезжайте, у нас как обычно по средам в 17.00 семинар;-)

Конкретно для x86 bsf или bsr (там же).

ты сам пишешь программу, формат массива и прочего можно менять, или он жестко задан?

Если можно менять, то лучше всего хранить битовую карту как массив int, как ты и написал, и при каждом удалении/добавлении очищать/поднимать соответствующий бит. Быстрее этого ты вряд ли что-нибудь придумаешь, потому что в остальных случаях придется обходить массив.

Вообще не очень понятно, что значит «быстро» в этом контексте. Потому что судя по всему описывается довольно сложный алгоритм, и время поиска первого ненулевого бита в числе не должно играть роли. Если все же играет, то сделай на асме, как сказали выше.