如何在R中实现大二进制数减法并判断结果是否为10的幂？

核心思路优化 #

因为texts_1是答对n题的集合，texts_2是答对n+1题的集合，两者的单处差异只能是texts_1中某题的0（答错）在texts_2中变成了1（答对），其他位置完全一致。利用这个特性可以大幅降低计算量，替代低效的adist全量对比。

方法一：哈希表快速匹配（推荐，速度最快） #

把texts_1存入哈希表，遍历texts_2的每个字符串，将其每个1位置改为0，检查修改后的字符串是否存在于texts_1中——存在即说明两者仅单处差异。

# 预处理：将texts_1转为哈希表（用命名向量实现快速查找）
texts1_hash <- setNames(seq_along(texts_1), texts_1)

# 存储结果
match_results <- list()

# 遍历texts_2的每个答案字符串
for (i in seq_along(texts_2)) {
  current_str <- texts_2[i]
  # 拆分为单个字符向量
  char_vec <- strsplit(current_str, "")[[1]]
  
  # 遍历每个字符位置，仅处理为1的位置（因为只有1改0才可能匹配texts_1的n题正确数）
  for (pos in seq_along(char_vec)) {
    if (char_vec[pos] == "1") {
      # 修改当前位置为0
      modified_vec <- char_vec
      modified_vec[pos] <- "0"
      modified_str <- paste(modified_vec, collapse = "")
      
      # 检查修改后的字符串是否在texts_1中
      if (modified_str %in% names(texts1_hash)) {
        match_results[[length(match_results) + 1]] <- data.frame(
          texts_1_index = texts1_hash[modified_str],
          texts_2_index = i,
          texts_1_answer = modified_str,
          texts_2_answer = current_str,
          diff_position = pos
        )
      }
    }
  }
}

# 合并结果为数据框
match_results <- do.call(rbind, match_results)

这个方法的时间复杂度是O(N*45)（N为texts_2的行数），对比原adist的O(M*N)（M为texts_1行数），速度提升几个数量级，30000行texts_2仅需几秒即可完成。

方法二：矩阵向量化运算 #

将字符串转为0/1整数矩阵，利用行和与元素级差异筛选符合条件的对：

# 将字符串转为0/1整数矩阵
mat1 <- do.call(rbind, strsplit(texts_1, "")) |> as.integer()
mat2 <- do.call(rbind, strsplit(texts_2, "")) |> as.integer()

# 校验行和（确保texts_1都是n题正确，texts_2都是n+1题正确）
n <- 你的正确题数n
mat1 <- mat1[rowSums(mat1) == n, ]
mat2 <- mat2[rowSums(mat2) == n+1, ]

match_results <- list()

# 遍历texts_2的每一行
for (i in seq_len(nrow(mat2))) {
  # 计算当前行与texts_1所有行的差异矩阵
  diff_mat <- mat2[i, ] - mat1
  # 筛选条件：差异总和为1（仅一处不同）且无负差异（只能是texts_1的0变texts_2的1）
  valid_rows <- rowSums(diff_mat) == 1 & rowSums(diff_mat < 0) == 0
  
  if (any(valid_rows)) {
    match_results[[i]] <- data.frame(
      texts_1_index = which(valid_rows),
      texts_2_index = i,
      texts_1_answer = texts_1[valid_rows],
      texts_2_answer = texts_2[i]
    )
  }
}

match_results <- do.call(rbind, match_results)

关于超大二进制数运算的补充 #

如果一定要通过二进制数减法判断差异，可使用gmp包处理大整数：

library(gmp)

# 二进制字符串转大整数
s1 <- "001111111111111101111011111111111111111111111"
s2 <- "001111111111111101111011111111111110111111111"

num1 <- as.bigz(s1, base = 2)
num2 <- as.bigz(s2, base = 2)

diff <- num1 - num2

# 判断是否为2的幂（对应二进制的10^k）
is_power_of_two <- function(x) {
  x > 0 && (x & (x - 1)) == 0
}

is_power_of_two(diff)  # 返回TRUE，说明仅单处差异

内容的提问来源于stack exchange，提问作者Mateus Figueiredo