加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

验证二进制数组是否是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.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读