c - 翻转C中的位

Question

最近在一次采访中，我被问到以下问题，但我无法正确回答。有人可以告诉我答案到底是什么吗？
问题:给定一个大小为 N 的数组。该数组的元素为 d[0],d[1]...d[N-1]，其中每个 d[i] 为 0 或 1。您最多可以执行数组上的一步:选择任意两个整数 [L,R] 并翻转第 L 和 R 位之间(包括)的所有元素。 L 和 R 代表标记您决定翻转的段边界的位的最左边和最右边的索引。

最终的位串中最多可以获得多少个 1 位(用 S 表示)？ “翻转”一点意思是，0 转换为 1，1 转换为 0。

示例输入810010010

示例输出6

Answer 1

这个怎么样？我假设 [L,R] 的定义是包含在内的，因此如果 L=5 且 R=2，您想要翻转位 2-5(包含在内)。

基本上，您构建一个掩码，其中要翻转的位置有 1，然后将其与原始整数进行异或。

int d = 0xdeadbeef; /* 0b11011110101011011011111011101111 */
int l = 5;
int r = 2;
int mask = 0;

for (int ii=r; ii<=l; i++) {
    mask |= 1<<ii;
}

printf("Original: %x", d);
printf("Bits %d-%d flipped: %x", r, l, d^mask) /* 0b11011110101011011011111011010011 */