Форум программистов, компьютерный форум CyberForum.ru

Обращение к элементам массива через биты некоторого числа - C++

Восстановить пароль Регистрация
 
 
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 18:02     Обращение к элементам массива через биты некоторого числа #1
Пусть есть массив Mass из 10 элементов и число А = 510 = 0...0 01012. Мне надо обратиться к 0 и 2 элементам (или к 7 и 9 - это как посмотреть) массива Mass. Можно ли как-нибудь через биты числа А получить доступ к элементам массива Mass?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2014, 18:02     Обращение к элементам массива через биты некоторого числа
Посмотрите здесь:

... В четных байтах числа в двоичной системе переместить нулевые биты в старшие биты, а в нечетных байтах – в младшие ... C++
C++ Обращение к элементам массива структур
Обращение к элементам двухмерного динамического массива C++
Обращение к элементам линейного списка через элементы массива указателей C++
Обращение к элементам класса через [] C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 18:22     Обращение к элементам массива через биты некоторого числа #2
Цитата Сообщение от mat_for_c Посмотреть сообщение
Можно ли как-нибудь через биты числа А получить доступ к элементам массива Mass?
Разве число А как-то связано с массивом Mass? Или нужно просто выяснить позиции установленных битов в числе А, а потом уже на основании этих позиций задать индекс к массиву?
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 20:05  [ТС]     Обращение к элементам массива через биты некоторого числа #3
Цитата Сообщение от Tulosba Посмотреть сообщение
нужно просто выяснить позиции установленных битов в числе А, а потом уже на основании этих позиций задать индекс к массиву?
Получается, что так. Только как это реализовать?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 20:09     Обращение к элементам массива через биты некоторого числа #4
Цитата Сообщение от mat_for_c Посмотреть сообщение
Только как это реализовать?
Элементарно. Хотя бы обычным сдвигом.
C++
1
2
3
4
5
int a = 5;
for( int i=0; i<sizeof(a); ++i )
{
   if( (a>>i) & 1 ) std::cout << i << std::endl; 
}
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 22:03  [ТС]     Обращение к элементам массива через биты некоторого числа #5
Цитата Сообщение от Tulosba Посмотреть сообщение
(a>>i) & 1 )
В чем смысл & 1 я понял. Меня все же смущает (a >> i). Если а = 32767, то программа выдаст только 0 1 2 3, когда должно быть 0 1 2 ... 12 13.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 22:16     Обращение к элементам массива через биты некоторого числа #6
mat_for_c, результат sizeof надо еще на 8 домножить.
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 22:26  [ТС]     Обращение к элементам массива через биты некоторого числа #7
Цитата Сообщение от Tulosba Посмотреть сообщение
надо еще на 8 домножить
Тогда все сходится А есть ли какой-нибудь быстрый способ?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 22:47     Обращение к элементам массива через биты некоторого числа #8
mat_for_c, а разве этот медленный?
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 23:08  [ТС]     Обращение к элементам массива через биты некоторого числа #9
Цитата Сообщение от Tulosba Посмотреть сообщение
а разве этот медленный?
Пока не знаю. Тогда сразу спрошу заодно...
На данный момент у меня самая затратная операция - это пересечение индексов массива (они упорядочены) через set_intersection (в цикле выполняется очень много раз). Подумал о таком подходе: индексы хранить в качестве битов, тем самым выиграю в пересечении через &, однако проиграю в извлечении самого индекса. Ваше мнение, так быстрее будет или нет смысла переписывать код?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 23:18     Обращение к элементам массива через биты некоторого числа #10
mat_for_c, я думаю, не стоит заниматься предварительной оптимизацией. Надо сделать какую-нибудь реализацию, а если она не устроит - искать узкие места профайлером.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
12.06.2014, 23:19     Обращение к элементам массива через биты некоторого числа #11
т.е. надо найти все единичные биты в числе?
обычно пишут еще так:
C++
1
2
3
4
5
for(int i = 0; i < 30; i++)
if(a && (1 << i))
{
//there is i-th bit in value a;
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,046
12.06.2014, 23:21     Обращение к элементам массива через биты некоторого числа #12
SlavaSSU, только Вы спутали логическое И (&&) с побитовым (&).
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 23:21  [ТС]     Обращение к элементам массива через биты некоторого числа #13
Цитата Сообщение от Tulosba Посмотреть сообщение
искать узкие места профайлером
искал - set_intersection и есть то самое место.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
12.06.2014, 23:29     Обращение к элементам массива через биты некоторого числа #14
да согласен, там тупанул. а насчет пересечения. если есть 2 множества индексов, то можно сделать из них числа, т.е. тупо перевести эти множества в числа. потом c = a & b; и где есть 1-ые биты в числе с, значит этот бит есть и в первом множестве и во втором. только я не знаю, быстрее это или нет
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 23:33  [ТС]     Обращение к элементам массива через биты некоторого числа #15
Цитата Сообщение от SlavaSSU Посмотреть сообщение
потом c = a & b
а я что имел ввиду под этим:
Цитата Сообщение от mat_for_c Посмотреть сообщение
индексы хранить в качестве битов, тем самым выиграю в пересечении через &
?

Добавлено через 1 минуту
Полагаю самый верный способ - переписать и сравнить скорость работы...
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
12.06.2014, 23:35     Обращение к элементам массива через биты некоторого числа #16
погоди! я не понял что дано! каждый раз тебе даны 2 числа, ты должен получить по этим числам индексы в массиве и найти пересечение индексов? или как?
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 23:39  [ТС]     Обращение к элементам массива через биты некоторого числа #17
Цитата Сообщение от SlavaSSU Посмотреть сообщение
каждый раз тебе даны 2 числа
2 множества индексов, их пересекаю и работаю в массиве только по пересеченным индексам
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
12.06.2014, 23:45     Обращение к элементам массива через биты некоторого числа #18
1)а как тебе даны множества???
сначала размер, а потом сами индексы, и аналогично для 2 множества?
вот тут не пойму!

2)и ты пихаешь в 1-ый сет первое множество, пихаешь во 2-ой сет индексы 2 множества и потом делаешь intersect?
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
12.06.2014, 23:51  [ТС]     Обращение к элементам массива через биты некоторого числа #19
индексы я формурую в зависимости от условий. кидаю их в разные вектора (их довольно много ~ 3000). Потом беру нужные 2 вектора с индексами, делаю пересечение, работаю с массивом, сохраняю пересечение и опять все по новой. и так много раз...
Цитата Сообщение от SlavaSSU Посмотреть сообщение
2)и ты пихаешь в 1-ый сет первое множество, пихаешь во 2-ой сет индексы 2 множества и потом делаешь intersect?
типа того, только в вектор
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2014, 00:01     Обращение к элементам массива через биты некоторого числа
Еще ссылки по теме:

Обращение к элементам массива используя указатель C++
Обращение к элементам динамического массива через указатели C++
Найти элементы массива, являющиеся квадратами некоторого числа C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
13.06.2014, 00:01     Обращение к элементам массива через биты некоторого числа #20
ага понятно!
я так понимаю изначально даны все множества?

тогда вот так можно сделать:

множество индексов не кидай в вектора, а делай из них число.

вот пусть дано множество и в нем n индексов, тогда получить число можно так.
вот ты считываешь все множества
C++
1
2
3
4
5
6
7
8
9
10
11
for(int j = 1; j <= cnt; j++)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int idx;
cin >> idx;
mask[j] |= (1 << idx);
}
}
теперь в mask[j] хранятся индексы j-ого множества.

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

ну все. пусть теперь надо пересечь i-ое и j-ое множества.

делаешь int Mask = mask[i] & mask[j];

и теперь все единичные биты в числе Mask - это и есть биты пересечения!
Yandex
Объявления
13.06.2014, 00:01     Обращение к элементам массива через биты некоторого числа
Ответ Создать тему
Опции темы

Текущее время: 15:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru