English 中文(简体)
一个获取下一个工作日设置位掩码的算法
原标题:
  • 时间:2008-12-08 23:50:12
  •  标签:

我有一个小问题 - 给定一组工作日的位掩码(例如,星期日= 0x01,星期一= 0x02,星期二= 0x04 等等...),和今天的日期(以星期日= 1,星期一= 2,星期二= 3 等形式表示),最优雅的方法是找到下一个设置在位掩码中的日期,而不是使用if/switch等语句。

编辑我可能应该提到(以使这更清楚),保存位掩码的变量可以设置几个日期,因此例如(粗略):

uDay = Sunday | Monday;
today = Tuesday;

我需要得到“星期天”

最佳回答
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;
}

那只是一个if和while循环。这样怎么样?

编辑:我刚刚意识到了一个退化的情况,即如果用户传递的today>=14(或大于最高位设置),那么while循环会变得无限。第4行上的(today%7)修复了这种情况。

如果可以轻松愉快地抱怨另一个版本获得了审核标记,我的版本只有2个模数调用,而被审核的解决方案将最少有1个模数调用和最多有6个模数调用。

另外,关于函数是否返回“今天”如果今天被设置了的评论是有趣的。如果函数不应该返回今天除非今天是集合中唯一的一天,那么需要在我解决方案的第3行预先递增今天。

问题回答

你根本不需要任何额外的变量。最简单的想法——从“明天”开始,查看连续的几天,直到找到一个在掩码中的日子——也是最优雅的实现方式。漂亮的做法的诀窍是将天数看作星期天=0,星期一=1等等(仅在此函数内部)。因此,“今天”实际上是t-1(其中t是函数的输入,因此它从1到7),而“明天”是(t-1+1)%7,即t%7等等。

这很简单,并已经经过彻底的测试,以确保它与litb s代码的兼容性。 :-)

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

我这样理解你的问题:

// 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

优雅的意思是,是否有不用if/switch等等的方法来完成这个?

当然没问题!但是是否符合通常意义上的优雅感,呃:

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;
}

那是假定你有优雅的功能来反转一个字中的位和查找最左边的已设置位 - 请参见Hacker's Delight。如果您按相反的顺序表示工作日位,则对于实际情况来说,它会更简单,甚至还有些优雅,假设我没有搞砸:

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;
}




相关问题
热门标签