验证二进制数组是否是C中另一个数组的子集
发布时间:2020-12-16 10:20:54 所属栏目:百科 来源:网络整理
导读:我需要验证字节数组(即字符)中的位是否是同一类型的另一个数组的子集:例如,0001.0011(19)是0011.0011(51)的子集,而0000.1011(11)不是. 我开始使用按位运算,几乎用XOR / OR / XOR序列解决它: int is_subset (char *set_a,char *set_b,int size){ /* The ope
我需要验证字节数组(即字符)中的位是否是同一类型的另一个数组的子集:例如,0001.0011(19)是0011.0011(51)的子集,而0000.1011(11)不是.
我开始使用按位运算,几乎用XOR / OR / XOR序列解决它: int is_subset (char *set_a,char *set_b,int size) { /* The operation is performed with three bitwise operations,resulting in a * sequence of bits that will be equal to zero if set_a is a subset of * set_b. As a bonus,the positions where the sets differ will be * available in the resulting sequence,and thus the number of differing * positions can be obtained by counting the number of bits set (for exemple,* with __builtin_popcount in GCC). * * Exemple (TRUE): Exemple (FALSE): * ================ ================ * set_a 00010011 set_a 00001011 * set_b 00110011 set_b 00110011 * ---------------- ---------------- * XOR 00100000 XOR 00111000 * set_b 00110011 set_b 00110011 * ---------------- ---------------- * OR 00110011 OR 00111011 * set_b 00110011 set_b 00110011 * ---------------- ---------------- * XOR 00000000 XOR 00001000 */ int i; for (i = 0; i < size; i++) if ( (((set_a[i] ^ set_b[i]) | set_b[i]) ^ set_b[i]) != 0) return FALSE; return TRUE; } 但如果set_a为零(0000.0000),则失败(始终返回TRUE).我尝试了不同的策略(比如Bloom过滤器),但可能由于我的编程技巧,它远非快速或至少优雅. 有没有例外的标准,优雅的方式吗? 编辑:要清楚,在此上下文中,“子集”意味着第一个数组(set_a)中的所有位TRUE在第二个数组(set_b)中也为TRUE.第二个数组中可能还有其他位为TRUE,但如果它们在第一个数组中为FALSE则无关紧要. 解决方法
我不确定你的代码是否失败是正确的,因为如果set_a是一个零数组,它返回TRUE,因为从纯粹的理论数学观点来看,空集是任何其他集的子集.如果您不喜欢,那么您应该添加额外的检查以查看set_a是否为零数组,如果是,则立即返回FALSE.
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |