How to design an efficient sign-in system

Suppose there is a monthly check-in activity now, and you want to record the monthly check-in data of users. If it was you, how would you design this feature?

In Java, a variable of type int occupies 4 bytes of space, and a byte has 8 bits (bit).

In other words, a variable of type int will take up 32b(it) of space. The value range of int: -2³¹ ~ 2³¹-1 (-2147483648~2147483647)

The maximum number of months in each month is 31 days. In February, basically ^[1]28 days in normal years and 29 days in leap years. They are all less than 32 (the 32 bits mentioned above).

Getting Started

Think about it, is it possible to use each bit of an int to store the check-in status of a certain day?

As shown in the figure below, assuming that there is a number 0 below, after converting it into binary, there are 32 0s, from the lowest digit to the highest digit, each number represents the check-in situation of a certain day:

1
 31th      26th      21th      16th      11th      6th      First
2
  ^         ^         ^         ^         ^         ^         ^
3
  |         |         |         |         |         |         |
4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0

E.g:

There is such an int number: 13030250, which is converted to binary as follows:

13030250（decimal）= 00000000 00110010 01101010 01101010（binary）

First of all, let’s set the rules, binary numbers, if a digit is 0, it means that it has not checked in, and if it is 1, it means that it has already checked in.

Combined with the converted binary numbers above (the signed-in data has been bolded). It can be seen that the 2nd, 4th, 6th, 7th, 10th, 12th, 14th, 15th, 18th, 21st, and 22nd days have already signed in (because the numbers in these digits are all 1), and the remaining days have not signed in .

When signing in, just change the number in the corresponding position to 1. To put it in layman’s terms, if you sign in on the first day, change the number in the first position to 1, and if you sign in on the nth day, change the number in the nth position to 1.

After the above demonstration, it can be seen that this design is completely feasible.

Coding

Before you start writing, you need to know the basic logic of bit operations. This is not complicated, so let’s not talk about it. Let’s talk about what is used in the project.

Let’s run the logic manually:

Suppose there is a variable value of 3351, ie: int value = 3351;

Convert it to binary: 3351_(decimal) = 00000000 00000000 00000111 00010111_(binary)

Then let’s take a look. The data of 00000000 00000000 00000111 00010111 indicates that the 1st, 2nd, 3rd, 5th, 9th, 10th, 11th day of this month has signed in. The rest of the day was unsigned.

Then again, we want to make ^[2] sign-in on the fourth day, which is equivalent to a supplementary sign. How should we change it?

First of all, we already know the requirements, that is, the fourth day to sign in, so that is, to operate the fourth bit of this binary data, see the following example: in order to facilitate the demonstration, the high bits of 0 are discarded

1
 00000000 00000000 00000111 00010111 ---------------------------> 111 00011011
2

3
 ========================================= PART 1 ============================================
4
       lowest bit
5
           ^
6
           |
7
 11100010111 >> (4-1) = 11100010    # Let the nth digit itself be shifted right (>>) n-1 bits
8
                      ^ 00000001    # XOR(^) 1 let its lowest bit (which is the fourth bit we want) change to 1
9
                      ----------
10
                        11100011    # Finally, lowest bit has chhanged to 1, Changing to 1 also means signing in
11

12
 ========================================= PART 2 ============================================
13
 11100011000 = (4-1) << 11100011    # Right to leat, Because the lower 3 bits were discarded above in order to handle the 4th digit, and are now to be restored, the left shift
14
|11100010111                        # an OR operation on this number after the left shift is complete
15
------------
16
 11100011111(result)                # We got the final result
17

18
 ========================================= PART 3 ============================================
19
 compare it：
20
 11100010111（initinal）
21
 11100011111（result）
22
 ------------------
23
        ^
24
        |
25
 4th, from 0 to 1, means un sign-in to signed-in

Four kinds of operations are used above, and the operation rules are explained below:

Shift left: Shift a few bits to the left, just add a few 0s at the end of the number
Shift right: shift a few bits to the right and discard the lowest bits
XOR operation: same as 0, different as 1
Logical OR: As long as one is 1, it is 1

Convert above process to code:

1
void sign(int day_of_month)
2
{
3
    int tmp = value;
4
    value = ((signStorage >> (day_of_month-1)) ^ 1) << (day_of_month-1) | tmp;
5
}

The sign-in has been mentioned above. Now let’s talk about how to check whether there is a sign-in on a certain day.

In fact, the check-in process is very similar to the check-in process, but the latter step is different.

In a nutshell, the sign-in process is:

1
graph LR
2
A[First move right to get the number of digits of the day you want to operate] -->B[Change the number 0 representing that day to 1]
3
    B --> C[left shift and OR operation restore the original data]

And the check-in process is

1
graph LR
2
A[First move right to get the number of digits of the day you want to operate] -->B{Determine whether the number of that day is 0 or 1}
3
    B --> |number=0| C[no sign-in]
4
    B --> |Number=1| D[Sign in]

Let’s walk through the process in detail: Let’s take the results calculated above as an example. The above calculation is: 11100011111. Now to judge whether there is a check-in on the third day, then:

1
 11100011111 >> (3-1) = 111000111 # For the 3rd day, shift right by (3-1) bits
2
                      & 000000001 # then &1
3
                      -------------
4
                        000000001 == 1 # If the result is equal to 1, it means that there is a check-in on the third day

Two kinds of operations are used above, and the operation rules are explained below (repetitions will not be explained):

Logical AND: The result is 1 only if both numbers are 1

Let’s take another example to determine whether there is a check-in on the 7th day:

1
 11100011111 >> (7-1) = 11100           # 求第7天，则右移(7-1)位
2
                      & 00001           # 然后&1
3
                  -----------
4
                        00000 == 0      # 结果等于0 则说明第7天没有签到

Let’s convert the above process into code:

1
int checkSign(int day_of_month)
2
{
3
    if (day_of_month <=0)
4
        day_of_month = get_cur_day();
5
    return (signStorage >> (day_of_month-1)) & 1;
6
}

Full code

C Language

1
#include <stdio.h>
2
#include <time.h>
3

4
int sign(int day_of_month);
5

6
int checkSign(int day_of_month);
7

8
int get_cur_day();
9

10
void dec2bin(int n);
11

12
int signStorage = 0;
13

14
int main()
15
{
16
    printf("BEFORE sign-in:\n");
17
    dec2bin(signStorage);
18
    for(int i = 1; i<=32 ;i++){
19
        sign(i);
20
    }
21

22
    printf("AFTER sign-in:\n");
23
    dec2bin(signStorage);
24

25
    printf("\nCHECK sign-in:\n");
26
    for(int i = 1; i<=32 ;i++){
27
        printf("Day %d sign-in: %d\n",i, checkSign(i));
28
    }
29

30
    return 0;
31
}
32

33

34
int sign(int day_of_month)
35
{
36
    int tmp = signStorage;
37
    if (day_of_month <=0)
38
        day_of_month = get_cur_day();
39
    else
40
        signStorage = ((signStorage >> (day_of_month-1)) ^ 1) << (day_of_month-1) | tmp;
41
    return 1;
42

43
}
44

45
int checkSign(int day_of_month)
46
{
47
    if (day_of_month <=0)
48
        day_of_month = get_cur_day();
49
    return (signStorage >> (day_of_month-1)) & 1;
50
}
51

52

53
int get_cur_day()
54
{
55
    time_t time_p;
56
    struct tm *p;
57
    time (&time_p);
58
    p=gmtime(&time_p);
59
    return p->tm_mday;
60
}
61

62
void dec2bin(int n){
63
    int c, k;
64
    for (c = 31; c >= 0; c--)
65
      {
66
        k = n >> c;
67

68
        if (k & 1)
69
          printf("1");
70
        else
71
          printf("0");
72
      }
73
      printf("\n");
74
}

Java Language

1
import java.util.Calendar;
2

3
public class SignDay {
4

5
    public static int signStorage = 0;
6

7
    public static void main(String[] args) {
8
        System.out.println("BEFORE sign-in:");
9
        System.out.println(Integer.toBinaryString(signStorage));
10
        for(int i = 1; i<=32 ;i++){
11
            sign(i);
12
        }
13
        System.out.println("\AFTER sign-in:");
14
        System.out.println(Integer.toBinaryString(signStorage));
15

16
        System.out.println("\nCHECK sign-in:");
17
        for(int i = 1; i<=32 ;i++){
18
            boolean signed = checkSign(i);
19
            if (signed) {
20
                System.out.println("Day " + i + " sign-in: " + signed);
21
            } else {
22
                System.err.println("Day " + i + " sign-in: " + signed);
23
            }
24
        }
25
    }
26

27

28
    public static boolean sign(int dayOfMonth){
29
        int tmp = signStorage;
30
        if (dayOfMonth <=0){
31
            dayOfMonth = Calendar.getInstance().get(Calendar.DAY_OF_MONTH);
32
        }
33
        if (dayOfMonth % 4 !=0){
34
            signStorage = ((signStorage >> (dayOfMonth-1)) ^ 1) << (dayOfMonth-1) | tmp;
35
        }
36
        // do other actions
37
        return false;
38
    }
39

40
    public static boolean checkSign(int dayOfMonth) {
41
        if (dayOfMonth <=0){
42
            dayOfMonth = Calendar.getInstance().get(Calendar.DAY_OF_MONTH);
43
        }
44
        return ((signStorage >> (dayOfMonth-1)) & 1) == 1;
45
    }
46

47
}

Tweet this article