Category Archives: 数据结构与算法

使用二进制进行权限控制

Posted on by

1，什么是二进制？

二进制是用0和1两个数码来表示的数，他的规则是“逢二进一”

比如：二进制00000000表示十进制0，00000001表示十进制1

2，如何使用权限控制？

二进制权限控制说的简单点，即是二进制与十进制之间的转换

用二进制表示权限值是按位来设置的，即每个位占一个权限，

比如：00000001表示第一位拥有一种权限（转为十进制权限为：1）

00000011表示第一位，第二位各拥有一种权限（转为十进制权限为3）

再比如：某个人拥有老师，班主任，教务主任3种权限，我们可以用二进制表示为：

00000111，用十进制表示为7

3，一个接口权限控制的例子。

要求：通过二进制权限控制不同来源的客户端（如：平板，手机，网页）登录的用户可以访问指定应用。

说明：目前有3个数据源（平板，手机，网页），他们对应的二进制权限位分别为 1, 2, 3

有一个用户user，他有属性：id，name，sex，power

一般接口会为每个数据源分配一个appKey，设置平板为appKey1，手机appKey2，网页appKey3。

假设我们设置用户user，可以通过平板和网页访问，即用二进制表示为00000101，用十进制表示：power = 5

程序实现：

使用binaryPosList 表示“二进制权限位集合”

for(int i=0;i<binaryPosList.size;i++) {
    power += pow(2,binaryPosList[i]-1);
}

private static int pow(int a, int N) {
    if(N == 0) {
        return 1;
    } else {
        return a*pow(a,N-1);
    }
}

所以power = pow(2,1-1) + pow(2,3-1) = 5;

当用户使用手机登录时：

接口通过传过来的appKey 查找到对应的二进制位为2，同时我们查找出此用户的权限power为5，二进制位00000101

首先说明下，当二进制最后一位为0时，转换为十进制必为偶数，当二进制最后一位为1时，转换为十进制必为奇数。

所以可以将power需要对比的位数移动到末尾，即将二进制数向右移动（二进制位-1），即移动后为：00000010，末尾移动的数丢弃，首位移动后用0补充。Java中正好有移位的算法。

Int n = power >>> (二进制位 -1)

若n为偶数（n % 2 == 0）则表示没有权限，若n为奇数则表示有权限。

常用排序（冒泡，选择，插入，快速）

Posted on by

算法：

1. 冒泡排序：

说明：外层循环以第1个元素为起点i，内层循环以第i+1为起点j,比较i和j对应的元素大小，只要有j元素小于i元素，则两者替换

代码示例：

public static int[] sort(int[] arr) {
        int temp = 0;
        for(int i=0;i<arr.length-1;i++) {
            for(int j=i+1;j<arr.length;j++) {
                if(arr[j] < arr[i]) {
                   temp = arr[i];
                    arr[i] = arr[j];
                   arr[j] = temp;
                }
            }
        }
        return arr;
}

 

2.选择排序：

说明：类似于冒泡排序，外层循环以第1个元素为起点i，内层循环以第i+1为起点j,先找出内层元素中最小的元素，两者替换（优于冒泡排序）

代码示例：

public static int[] sort(int[] arr) {
        int temp = 0;
        for(int i=0;i<arr.length-1;i++) {
            int lowIndex = i;
            for(int j=i+1;j<arr.length;j++) {
                if(arr[j] < arr[lowIndex]) {
                   lowIndex = j;
                }
            }

            temp = arr[i];
            arr[i] = arr[lowIndex];
            arr[lowIndex] = temp;
        }
        return arr;
}

 

3.插入排序：

图解：

1

2

代码示例：

public static int[] sort(int[] arr) {
    int temp = 0;
    for(int i=1;i<arr.length;i++) {
        for(int j=0;j<i;j++) {
        if(arr[i] < arr[j]) {
           temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
        }
        }
    }
    return arr;
}

 

4.快速排序：

图解：

3

代码示例：

    public static int getPoint(int[] arr, int low, int high) {
        int point = low;
        int contrast = arr[point];
        for (int i = low + 1; i <= high; i++) {
            if (arr[i] < contrast) {
                point++;
                swap(arr, point, i);
            }
        }
        swap(arr, low, point);
        return point;
    }

    public static int[] quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int point = getPoint(arr, low, high);
            quickSort(arr, low, point - 1);
            quickSort(arr, point + 1, high);

        }

        return arr;
    }