給定二進位制字串中從左起第一個設定位的位置，其中所有 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 都出現在末尾。