位运算在高级语言里面也是一个很好的东西

最近屌丝的公司想要为以前的那个网页产品加上一个过滤的功能,废话不多说,直接看筛选的界面是啥样的吧:

Capture

可以看出,我们的Message分为Critical、Error等6种类型。现在需要进行过滤,用户可以选择查看其中的一项或多项。

这种需求是很常见的,在大多数情况下,如果可选项是不固定的(比如对于学生信息管理系统,按照班级进行筛选),那么就可能需要借助复杂的SQL语句。例如我们可以写成如下这种形式:

SELECT * FROM [Student] WHERE [ClassId] = 1 OR [ClassId] = 2 OR...

这样就要对SQL语句进行拼接,根据用户选择了哪些内容来动态生成SQL语句。

假如不是数据库操作,而是内存中一片数据的判断,假如用户选择的内容存放在Selected[]数组中,那么对于需要判断的每一项,我们都需要进行一连串的判断操作,需要写一个双重循环。不仅写起来比较复杂,如果项目过多在效率上也令人堪忧。

如果我们需求是像上图那样,Type是固定的并且也不会很多,那么有没有一种比较简单的方式呢?

从标题可以看出,可以使用位运算。在各类高级语言的源代码中大量地运用了这种方式。对于可枚举类型,取值不是顺序的1、2、3、4,而是1、2、4、8按照2的倍数增长,这就是使用二进制位进行判断。

现在我用我刚做的东西来简单叙述一下如何实现吧。当然实现这个很简单,在这里记录更多地是为了增加博文的数量^_^。

在.NET中,一个int类型占4个字节,也就是32位,除去符号位(当然也可以使用无符号整数,这里为了简单期间都使用int),每一位都可以标识一个消息的类型。为此,我们定义枚举类型如下:

    public enum CategoryType: int
    {
        Unknown = 1,
        Critical = 2,
        Error = 4,
        Warning = 8,
        Information = 16,
        Verbose = 32,
        Other = 1024
    }

如果用二进制表示,这些消息分别是0000 0001、0000 0010、0000 0100、0000 1000、00010000、…… 假如用户选择了Unknown、Error和Waring三种类型,把这三个数字相加,就是1+4+8=13,二进制表示就是0000 1101。为1的位正好对应了用户选择的类型,为0的位正好对用用户没选的类型。

在客户端,使用Javascript就可以使用下面这种简单的方式计算用户选择的值:

            var category = 0;

            if (filterVM.ckType2Checked()) category |= 2;
            if (filterVM.ckType4Checked()) category |= 4;
            if (filterVM.ckType8Checked()) category |= 8;
            if (filterVM.ckType16Checked()) category |= 16;
            if (filterVM.ckType32Checked()) category |= 32;
            if (filterVM.ckType1024Checked()) category |= 1024;

当然,由于这种特殊的设计,使用加法运算的效果是完全相同的。

这样把用户选择的内容传给服务器就是一个简单的整数,比如上面的13表示用户选择的三种类型。而且在数学上可以证明,对于每一个整数,对应的枚举类型的组合是唯一的(要证明看似很难,但如果使用二进制进行思考便会显而易见)。

在服务器端对每种消息进行判断时,只需要使用与运算,便能知道消息是否在用户选择的范围内(只要结果不等于0,说明某个枚举类型对应的那一位在相加的结果中。如果使用符号位,那么可能会出现负数)。

举两个简单的例子吧,假如客户端传过来的是13(0000 1101),某一种消息是Waring=8(0000 1000),相与的结果为8(0000 1000)与消息的类型相同(只需判断是否不等于0即可)。对于消息为16(0001 0000)的情况,相与的结果肯定是0。代码如下:

            for (int i = 0; i < list.Count; i++)
            {
                if (((int)list[i].Category & categoryFilter) > 0 && ((int)list[i].Direction & directionFilter) > 0)
                    yield return list[i];
            }

对于要选出所有的类型的情况,只需要把上述categoryFilter设置为全部为1的数字即可(0x7fffffff,如果使用符号位就是0xffffffff)。

在客户段根据这个相加后的结果进行控件绑定的使用,要判断某个复选框是否应该选中时,按照相同的逻辑相与即可:

            this.ckType2Checked((category & 2) > 0);
            this.ckType4Checked((category & 4) > 0);
            this.ckType8Checked((category & 8) > 0);
            this.ckType16Checked((category & 16) > 0);
            this.ckType32Checked((category & 32) > 0);
            this.ckType1024Checked((category & 1024) > 0);

 

需要注意的是,这个方法不是万能的。如果可选项是不固定的,使用位运算有可能反而会很麻烦,因为我们要编写程序存储每一种选项对应的数字。

如果可选项是固定的但是数量很多(比如几千种),那么我们可以用一串整数进行表示,也会很方便(当然显示也不会有这样变态的筛选功能,即使有用户也不大可能在几千种里面去选,如果出现这种情况,只能说设计有问题)。

这种做法有一个比较大的弊端,就是改动筛选内容时服务器和客户端都会改。不过还好改动不会太大,只需要改变服务器的enum和客户端的控件即可……

当然这种思想也是今后设计程序时的一种很好参考。

位运算在高级语言里面也是一个很好的东西”的一个响应

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s