Determine which bit is set, for a date, using complex bit masks

Question

I have a bit shift mask that represents days in a week:

Sunday = 1
Monday = 2
Tuesday = 4
...
Saturday = 64

I'm using a bitmask because several (at least one) days may be set to 1.

The problem

Then I get a date. Any date. And based on the date.DayOfWeek I need to return the first nearest date after it that is set in the bitmask. So my method can return the same day or any other day between date and date + 6.

Example 1

My bitmask defines all days being set to 1. In this case my method should return the same date, because date.DayOfWeek is set in the bitmask.

Example 2

My bitmask defines that only Wednesday is set to 1. If my incoming date is Tuesday, I should return date+1 (which is Wednesday). But if incoming date is Thursday I should return date+6 (which is again Wednesday).

Question

What is the fastest and most elegant way of solving this? Why also fastest? Because I need to run this several times so if I can use some sort of a cached structure to get dates faster it would be preferred.

Can you suggest some guidance to solve this in an elegant way? I don't want to end up with a long spaghetti code full of ifs and switch-case statements...

Important: It's important to note that bitmask may be changed or replaced by something else if it aids better performance and simplicity of code. So bitmask is not set in stone...

A possible approach

It would be smart to generate an array of offsets per day and save it in a private class variable. Generate it once and reuse it afterwards like:

return date.AddDays(cachedDayOffsets[date.DayOfWeek]);

This way we don't use bitmask at all and the only problem is how to generate the array the fastest and with as short code as possible.

Answer 1

I'd go about this with a bitmask, some shifting, and a bitscan. It's not a very obvious routine, but it should be fast, as it never branches:

original_date = Whatever                    //user input
bitmask = Whatever                          //user input
bitmask |= (bitmask << 7)                   //copy some bits so they don't get
                                            //lost in the bitshift
bitmask >>= original_date.dayOfWeek()       //assuming Sunday.dayOfWeek() == 0
return original_date + bitscan(bitmask) - 1 //the position of the least
                                            //significant bit will be one greater
                                            //than the number of days to add

Bitscan - especially yours, 'cause it only cares about seven bits - is easy to implement in a lookup table. In fact, if you did a custom table, you could call the LSB bit 0, and skip the subtraction in the return statement. I'd guess the slowest part of all of this would be the dayOfWeek() function, but that would depend on it's implementation.

Hope this helps!

Edit: An example bitscan table (that treats the lsb as index 1 - you'll probably want to treat it as zero, but this makes a better example):

int[128] lsb = {
    0, //0 = 0b00000000 - Special case!
    1, //1 = 0b00000001
    2, //2 = 0b00000010
    1, //3 = 0b00000011
    3, //4 = 0b00000100
    1, //5 = 0b00000101
    2, //6 = 0b00000110
    ....
    1 //127 = 0b01111111
};

Then, to use your table on mask, you'd just use:

first_bit_index = lsb[mask & 127];

The & lets you write a smallish table, 'cause you really only care about the seven lowest bits.

PS: At least some processors implement a bitscan instruction that you could use instead, but it seems unlikely that you could get at them with C#, unless there's a wrapper function somewhere.

Answer 2

You might hate this answer, but perhaps you'll be able to run with it in a new direction. You said performance is extremely important, so maybe it's best to just index all the answers up front in some data structure. That data structure might be somewhat convoluted, but it could be encapsulated in its own little world and not interfere with your main code. The data structure I have in mind would be an array of ints. If you allow Monday, Friday, and Saturday, those ints would be:

[1][0][3][2][1][0][0]

Ok weird right? This is basically the "days away" list for the week. On Sunday, there's "1 day until next allowed day of week". On Monday, there's 0. On Tuesday, it's 3 days away. Now, once you build this list, you can very easily and very quickly figure out how many days you need to add to your date to get the next occurance. Hopefully this helps??

Generating these offsets

This is the code that generates these offsets:

this.dayOffsets = new int[] {
    this.Sundays ? 0 : this.Mondays ? 1 : this.Tuesdays ? 2 : this.Wednesdays ? 3 : this.Thursdays ? 4 : this.Fridays ? 5 : 6,
    this.Mondays ? 0 : this.Tuesdays ? 1 : this.Wednesdays ? 2 : this.Thursdays ? 3 : this.Fridays ? 4 : this.Saturdays ? 5 : 6,
    this.Tuesdays ? 0 : this.Wednesdays ? 1 : this.Thursdays ? 2 : this.Fridays ? 3 : this.Saturdays ? 4 : this.Sundays ? 5 : 6,
    this.Wednesdays ? 0 : this.Thursdays ? 1 : this.Fridays ? 2 : this.Saturdays ? 3 : this.Sundays ? 4 : this.Mondays ? 5 : 6,
    this.Thursdays ? 0 : this.Fridays ? 1 : this.Saturdays ? 2 : this.Sundays ? 3 : this.Mondays ? 4 : this.Tuesdays ? 5 : 6,
    this.Fridays ? 0 : this.Saturdays ? 1 : this.Sundays ? 2 : this.Mondays ? 3 : this.Tuesdays ? 4 : this.Wednesdays ? 5 : 6,
    this.Saturdays ? 0 : this.Sundays ? 1 : this.Mondays ? 2 : this.Tuesdays ? 3 : this.Wednesdays ? 4 : this.Thursdays ? 5 : 6
};

This one generates forward offsets. So for any given date you can get the actual applicable date after it by simply:

SomeDate.AddDays(this.dayOffsets[(int)SomeDate.DayOfWeek]);

If you need to get nearest past date you can reuse the same array and calculate it out by using this formula:

SomeDate.AddDays((this.dayOffsets[(int)SomeDate.DayOfWeek] - 7) % 7);