Determine which bit is set for the date using complex bit masks

Question

I have a small replaceable mask that represents the days of the week:

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

I use a bitmask because several (at least one) days can be set to 1.

Problem

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

Example 1

My bitmask determines that all days are set to 1. In this case, my method should return the same date because date.DayOfWeek set in the bitmask.

Example 2

My bitmask determines that only the environment is set to 1. If my incoming date is Tuesday, I must return date+1 (this is Wednesday). But if the incoming date is Thursday, I have to return date+6 (this is again Wednesday).

Question

What is the fastest and most elegant way to resolve this issue? Why so fast? Since I need to run this several times, so if I can use some kind of cached structure to speed up dates, it would be preferable.

Can you offer some recommendations to solve this in an elegant way? I don't want the result to be a long spaghetti code filled with ifs and switch-case statements ...

It is important . It is important to note that the bitmask can be changed or replaced with something else if it helps to improve the performance and simplicity of the code. So, the bitmask is not installed in the stone ...

Possible approach

It would be wise to generate an array of offsets per day and store it in a private class variable. Create it once and reuse it, for example:

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

Thus, we do not use a bitmask at all, and the only problem is how to generate the array as quickly as possible and with short code.

Answer 1

You may hate this answer, but perhaps you can work with it in a new direction. You said that performance is extremely important, so it might be best to index all the answers to the forefront in some data structure. This data structure may be somewhat confusing, but it can be encapsulated in your own world and not interfere with your main code. The data structure that I mean is an array of ints. If you allow Monday, Friday and Saturday, they will be:

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

Good odd? This is basically a weekly weekly list. On Sunday there is "1 day until the next authorized day of the week." On Monday, there is 0. On Tuesday, this is 3 days. Now, once you create this list, you can very easily and very quickly find out how many days you need to add to your date in order to receive the next incident. Hope this helps?

Creating 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 generates offsets forward. Therefore, for any date, you can get the actual applicable date after it simply:

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

If you need to get the closest past date, you can reuse the same array and calculate it using this formula:

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

Answer 2

I would do it with a bit mask, a few offsets and bits. This is not a very obvious routine, but it should be fast, since 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 because it only cares about seven bits - is easy to implement in a lookup table. In fact, if you created a user table, you can invoke the LSB 0 bit and skip the subtraction in the return statement. I think the slowest part of all this will be the dayOfWeek () function, but it will depend on its implementation.

Hope this helps!

Edit: An example bitcan table (which treats lsb as index 1 - you probably want to treat it as zero, but this is 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 the table in mask , you simply use:

 first_bit_index = lsb[mask & 127]; 

& allows you to write a small table, because you really only care about the seven least significant bits.

PS: At least some processors implement the bitcan instruction, which you could use instead, but you could hardly get them using C # if there is no shell function there.

Answer 3

Here is the algorithm for filling the search table. You only need to do this once, so I'm not sure if it matters how effective it is ...

 int[] DaysOfWeek = (int[])Enum.GetValues(typeof(DayOfWeek)); int NumberOfDaysInWeek = DaysOfWeek.Length; int NumberOfMasks = 1 << NumberOfDaysInWeek; int[,] OffsetLookup = new int[NumberOfDaysInWeek, NumberOfMasks]; //populate offset lookup for(int mask = 1; mask < NumberOfMasks; mask++) { for(int d = 0; d < NumberOfDaysInWeek; d++) { OffsetLookup[d, mask] = (from x in DaysOfWeek where ((1 << x) & mask) != 0 orderby Math.Abs(x - d) select (x - d) % NumberOfDaysInWeek).First(); } } 

Then just use:

 DateTime SomeDate = ...; //get a date DateTime FirstDate = SomeDate.AddDays(OffsetLookup[SomeDate.DayOfWeek, DayOfWeekMask]); 

Answer 4

Here is what I would do, the dateDiff variable dateDiff be what you are looking for.

 DoW mask = DoW.Wednesday | DoW.Friday; DoW? todayDoW = null; int dateDiff = 0; do { DateTime date = DateTime.Today.AddDays(dateDiff); todayDoW = (DoW)Enum.Parse(typeof(DoW), date.DayOfWeek.ToString()); if ((mask & todayDoW.Value) != 0) { todayDoW = null; } else { dateDiff++; } } while(todayDoW.HasValue); enum DoW { Sunday = 1, Monday = 2, Tuesday = 4, Wednesday = 8, Thursday = 16, Friday = 32, Saturday = 64 } 

Answer 5

This should be pretty easy to do. Consider DayOfWeek.Sunday == 0 , Monday == 1 , etc.

Your mask matches that. That is, in your mask:

 Sunday = 1 << 0 Monday = 1 << 1 Tuesday = 1 << 2 

Now, given the day of the week, we can easily determine the day that will meet your criteria:

 [Flags] enum DayMask { Sunday = 1, Monday = 2, Tuesday = 4, Wednesday = 8, Thursday = 16, Friday = 32, Saturday = 64 } static DayOfWeek FindNextDay(DayMask mask, DayOfWeek currentDay) { DayOfWeek bestDay = currentDay; int bmask = 1; for (int checkDay = 0; checkDay < 7; ++checkDay) { if (((int)mask & bmask) != 0) { if (checkDay >= (int)currentDay) { bestDay = (DayOfWeek)checkDay; break; } else if (bestDay == currentDay) { bestDay = (DayOfWeek)checkDay; } } bmask <<= 1; } return bestDay; } 

For example, the day you want to combine is Wednesday, but the mask contains only Monday. You can see that the algorithm will select Monday as the best day, and then go through the remaining days without selecting anything.

If the mask contains Monday, Tuesday, and Thursday, the algorithm will select Monday as the best candidate, ignore Tuesday, and then select Thursday as the best candidate and exit.

It won't be as fast as the lookup table, but it should be damned quickly. And it will use a lot less memory than the lookup table.

The lookup table will be much faster, and it will not take up only a kilobyte of memory. And given the FindNextDay method above, it's easy enough to build:

  static byte[,] LookupTable = new byte[128, 7]; static void BuildLookupTable() { for (int i = 0; i < 128; ++i) { DayMask mask = (DayMask)i; for (int day = 0; day < 7; ++day) { LookupTable[i, day] = (byte)FindNextDay(mask, (DayOfWeek)day); } } } 

Now, to get the next day for any combination of mask and current day:

 DayOfWeek nextDay = (DayOfWeek)LookupTable[(int)mask, (int)currentDay]; 

This is undoubtedly a quick way to generate a table. But it is fast enough and, since it will be executed once when the program starts, there is no point in optimizing it. If you want the launch to be faster, write a small program that displays the table as C # code. Something like:

 Console.WriteLine("static byte[,] LookupTable = new byte[128,7] {"); for (int i = 0; i < 128; ++i) { Console.Write(" {"); for (int j = 0; j < 7; ++j) { if (j > 0) { Console.Write(","); } Console.Write(" {0}", LookupTable[i, j]); } Console.WriteLine(" },"); } Console.WriteLine("};"); 

Then you can copy and paste it into your program.

Answer 6

I understand that you said that performance should be taken into account, but I would like to start with a simple, understandable approach and check if its performance is sufficient before moving on to a more complex method that may leave future code accompanying bits lost.

Having said that, a solution using pre-initialized searches is possible:

 [Flags] enum DaysOfWeek { None = 0, Sunday = 1, Monday = 2, Tuesday = 4, Wednesday = 8, Thursday = 16, Friday = 32, Saturday = 64 } 

Assuming the previous listing:

 private static Dictionary<DayOfWeek, List<DaysOfWeek>> Maps { get; set; } static void Main(string[] args) { Maps = CreateMaps(); var date = new DateTime(2011, 9, 29); var mask = DaysOfWeek.Wednesday | DaysOfWeek.Friday; var sw = Stopwatch.StartNew(); for (int i = 0; i < 10000; i++) { GetNextDay(date, mask); } sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } private static DaysOfWeek GetNextDay(DateTime date, DaysOfWeek mask) { return Maps[date.DayOfWeek].First(dow => mask.HasFlag(dow)); } 

And finally, the implementation of CreateMaps :

 private static Dictionary<DayOfWeek, List<DaysOfWeek>> CreateMaps() { var maps = new Dictionary<DayOfWeek, List<DaysOfWeek>>(); var daysOfWeek = new List<DaysOfWeek>(7) { DaysOfWeek.Sunday, DaysOfWeek.Monday, DaysOfWeek.Tuesday, DaysOfWeek.Wednesday, DaysOfWeek.Thursday, DaysOfWeek.Friday, DaysOfWeek.Saturday }; foreach (DayOfWeek dayOfWeek in Enum.GetValues(typeof(DayOfWeek))) { var map = new List<DaysOfWeek>(7); for (int i = (int)dayOfWeek; i < 7; i++) { map.Add(daysOfWeek[i]); } for (int i = 0; i < (int)dayOfWeek; i++) { map.Add(daysOfWeek[i]); } maps.Add(dayOfWeek, map); } return maps; }