Алгоритм получения следующего дня недели в битовой маске

Question

У меня есть этот маленький вопрос - учитывая битовую маску будних дней (например, Sunday = 0x01, Monday = 0x02, Tuesday = 0x04 и т. Д.) И сегодняшнего дня (в форме Sunday = 1, Monday = 2, Tuesday = 3 и т. Д.) - что является самым элегантным способ узнать на следующий день с сегодняшнего дня, который установлен в битовой маске? Под элегантным я имею в виду, есть ли способ сделать это без if / switch / etc ..., потому что я знаю не элегантный способ?

Редактировать Вероятно, я должен был упомянуть (чтобы сделать это более понятным), что для переменной, содержащей битовую маску, может быть установлено несколько дней, например (примерно):

uDay = Sunday | Monday;
today = Tuesday;

Мне нужно получить "воскресенье"

Answer 1

int getNextDay(int days_mask, int today) {
   if (!days_mask) return -1; // no days set
   days_mask |= days_mask << 7; // duplicate days into next week
   mask = 1 << (today % 7); // keep track of the day
   while (!(mask & days_mask)) {
      mask <<= 1;
      ++today;
   }
   return today % 7;
}

Так что это только один, если в начале и в то время как цикл. Как это?

Редактировать: Я только что понял, что был вырожденный случай, когда, если использование проходит сегодня> = 14 (или больше, чем самый высокий установленный бит), цикл while становится бесконечным. (Сегодня% 7) в строке 4 исправляет этот случай.

И если я могу (без энтузиазма) ворчать о том, что другая версия получает галочку, моя версия имеет только 2 вызова модуля, в то время как проверенное решение будет иметь минимум 1 и максимум 6 вызовов модуля.

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

Answer 2

Вам не нужны никакие дополнительные переменные вообще. Самая простая идея - начать с «завтра», смотреть на последовательные дни, пока вы не найдете день в маске - также является наиболее элегантной для реализации. Хитрость в этом заключается в том, чтобы думать о днях как воскресенье = 0, понедельник = 1 и т. Д. (Только внутри этой функции). Тогда «сегодня» на самом деле равно t-1 (где t - это входные данные для функции, то есть от 1 до 7), а «завтра» - это (t-1+1)%7 т.е. t%7 и т. Д.

Это просто и исчерпывающе проверено на коде litb, просто чтобы быть уверенным: -)

int getNextDay(int m, int t) {
  if((m&127)==0) return t;          //If no day is set, return today
  t=t%7;                            //Start with tomorrow
  while((m&(1<<t))==0) t = (t+1)%7; //Try successive days
  return t+1;                       //Change back to Sunday=1, etc.
}

Редактировать: если вы хотите, чтобы «следующий» означал «сегодня или позже», тогда строку «t = t% 7» следует изменить на t=t-1 или --t.

Answer 3

Под элегантностью я имею в виду, есть ли способ сделать это без if / switch / etc ...

Вы держите пари! Будет ли это означать «элегантный» в любом обычном смысле, хорошо:

static unsigned next_day_set (unsigned today, unsigned set) {
  unsigned arev = bitreverse (highest_bit_set (bitreverse ((set << 7) | set)
                                               & (bitreverse (today) - 1)));
  return ((arev >> 7) | arev) & 0x7f;
}

Это предполагает, что у вас есть «элегантные» функции для обращения битов в слове и поиска самого левого набора битов - см. Восторг хакера . Если бы вы представляли биты дня недели в обратном порядке, это было бы проще и даже на самом деле даже нарядно, если бы я не облажался:

enum {
  Sunday  = 1 << 6
  Monday  = 1 << 5
  Tuesday = 1 << 4,
  /* etc */
  Saturday = 1 << 0
};

static unsigned next_day_set (unsigned today, unsigned set) {
  unsigned a = highest_bit_set (((set << 7) | set) & ((today << 7) - 1));
  return ((a >> 7) | a) & 0x7f;
}

Answer 4

Я так понимаю ваш вопрос:

// returns t (today) if no weekday is set in the mask.
int getNextDay(int m, int t) {
    int i, idx;
    for(i = 0, idx=t%7; i<7 && !((1<<idx)&m); i++, idx=(idx+1)%7)
        /* body empty */ ;
    return (i == 7) ? t : (idx + 1);
}

// getNextDay(8|2, 2) == 4, getNextDay(64, 2) == 7
// getNextDay(128, 2) == 2