给定二进制字符串中从左起第一个设置位的位置，其中所有 1 都出现在末尾

---

本文旨在实现一个程序，用于查找给定二进制字符串中从左起第一个设置位的位置，其中所有 1 都出现在末尾。

位字符串称为二进制字符串。与通常保存文本数据的字符字符串不同，二进制字符串用于存储非传统数据，例如图像。二进制字符串的长度由其字节数决定。

在计算机编程中，二进制数据（以二进制（基数 2）而不是文本（基数 10）格式表示的数据）存储在二进制字符串变量中。

给定一个长度为 L 的二进制字符串 Str，其中所有 1 都排列在最右边。如果从左侧无法检测到任何设置位，则应返回 -1。

示例 1

Let us take the Input string:
str = 0000111
With size, l = 7
Output obtained in this case is: 4

说明 − 索引 4 对应于从左侧算起的第一个设置位。

示例 2

Let us take the Input string:
str = 0111
With size, l = 4
Output obtained in this case is: 1

说明 − 索引 1 对应于从左侧算起的第一个设置位。

示例 3

Let us take the Input string:
str = 001
With size, l = 3
Output obtained in this case is: 2

说明 − 索引 2 对应于从左侧算起的第一个设置位。

示例 4

Let us take the Input string:
str = 0001
With size, l = 4
Output: 3

说明 − 索引 3 对应于从左侧算起的第一个设置位。

问题陈述

实现一个程序，以获取给定二进制字符串中从左起第一个设置位的位置，其中所有 1 都出现在末尾。

方法

解决此问题并获取给定二进制字符串中从左起第一个设置位位置的方法是应用二分查找技术。

让我们简要了解一下二分查找技术。

通过不断将搜索区间减半，可以使用二分查找算法搜索排序数组。利用每个数组都已排序的知识，二分查找试图将时间复杂度降低到 O(log N)。

算法

下面给出了实现程序以获取给定二进制字符串中从左起第一个设置位位置的算法，其中所有 1 都出现在末尾

• 步骤 1 − 定义一个函数“isBitSet”以确定位是否已设置。

• 步骤 2 − 定义一个函数“findFirstBit”以确定第一个设置位的位置。

• 步骤 3 − 定义整数变量 left、right、mid 和 res。然后实现二分查找技术。

• 步骤 4 − 返回获得的第一个设置位的位置作为结果。

示例（C 程序）

以下是上述算法的 C 语言程序实现，用于获取给定二进制字符串中从左起第一个设置位的位置，其中所有 1 都出现在末尾。

#include <stdio.h>
#include <string.h>
int isBitSet(char *str, int i){
   return str[i] == '1';
}
int findFirstBit(char* str, int l){
   int left = 0, right = l, mid, res = -1;
   while (left <= right) {
      mid = (left + right) / 2;
      if (isBitSet(str, mid)) {
         res = mid;
         right = mid - 1;
      }
      else {
         left = mid + 1;
      }
   }
   return res;
}
int main(){
   char str[] = "01111";
   int l = strlen(str);
   printf("%d
", findFirstBit(str, l));
   return 0;
}

输出

执行后，将产生以下输出：

1

结论

同样，我们可以实现一个程序来获取给定二进制字符串中从左起第一个设置位的位置，其中所有 1 都出现在末尾。本文解决了在给定二进制字符串中获取从左起第一个设置位位置的挑战，其中所有 1 都出现在末尾。这里提供了 C 语言代码以及获取给定二进制字符串中从左起第一个设置位位置的方法和算法，其中所有 1 都出现在末尾。