Блог пользователя rembocoder

Автор rembocoder, история, 5 лет назад, По-русски

В этой теме описано, как пройтись по всем подмаскам данной маски без дополнительных памяти и времени. Мне стало нужно сделать то же самое для надмасок, но я не нашёл ничего подобного. Исходя из формулы mask ^ (~mask) = -1, мой брат сгенерировал следующий код:

    for (int over = (1 << n) - 1; over > 0; over = ((over - mask - 1) & ~mask) + mask) {
        cout << over << " ";
    }

Это и правда работает. Но нельзя ли это как-то упростить, чтобы было легче вспомнить это на контесте?

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем rembocoder (предыдущая версия, новая версия, сравнить).

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

Пройдитесь по всем подмаскам инверсии данной, а в ответ выводите ксор текущей и данной.

int inversion = (1 << n) - 1 & ~mask;
for (int i = inversion; i > 0; i = (i - 1) & inversion) 
    cout << i ^ mask;
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, это более простая версия для запоминания той же идеи)

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
5 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

There is an easier code ==>

for(int over = mask;over > 0;over = (over -1) & mask) cout << over << " ";

Also, you can prove it by induction.

»
5 лет назад, # |
  Проголосовать: нравится +94 Проголосовать: не нравится
for (int mask = need; mask < (1 << n); mask = (mask + 1) | need) {

}
»
5 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

you want the overmasks of $$$S$$$ (i.e.: the masks of which $$$S$$$ is submask). I think it's the same as the NOT ($$$\text{~}$$$) of submasks of $$$\text{~} S$$$. Correct me if I'm wrong.

»
4 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

This post has no comment newer than 8 months ago. How did it appear under "Recent actions"?