亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

提高字符串到二進制數轉換的性能

提高字符串到二進制數轉換的性能

慕妹3146593 2023-09-20 16:43:34
這是我在競爭性編程中遇到的問題之一。問題)您有一個二進制格式的輸入字符串11100,您需要計算數字為零的步驟數。如果數字是odd -> subtract it by 1,如果even -> divide it by 2。例如28 -> 28/214 -> 14/27 -> 7-16 -> 6/23 -> 3-12 -> 2/21-> 1-10 -> 停止步數=7我想出了以下解決方案public int solution(String S) {    // write your code in Java SE 8    String parsableString = cleanString(S);    int integer = Integer.parseInt(S, 2);    return stepCounter(integer);}private static String cleanString(String S){    int i = 0;    while (i < S.length() && S.charAt(i) == '0')        i++;    StringBuffer sb = new StringBuffer(S);    sb.replace(0,i,"");    return sb.toString();}private static int stepCounter(int integer) {    int counter = 0;    while (integer > 0) {        if (integer == 0)            break;        else {            counter++;            if (integer % 2 == 0)                integer = integer / 2;            else                integer--;        }    }    return counter;}這個問題的解決方案看起來非常簡單明了,但是這段代碼的性能評估給了我一個大零。我最初的印象是,將字符串轉換為 int 是一個瓶頸,但未能找到更好的解決方案。有人可以向我指出這段代碼的瓶頸以及可以顯著改進的地方嗎?
查看完整描述

3 回答

?
慕標琳琳

TA貢獻1830條經驗 獲得超9個贊

如果二進制數是奇數,則最后一位(最低有效位)必須是1,因此減 1 就是將最后一位數字從 1 更改為 0(重要的是,這使數字成為偶數)。

如果二進制數是偶數,則最后一位必須為0,除以零只需完全刪除最后一位 0 即可完成。(就像以 10 為基數一樣,數字 10 可以除以 10,去掉最后的 0,留下 1。)

所以步數是每 1 位數字兩步,每 0 位數字一步 - 減 1,因為當你到達最后一個 0 時,你不再除以 2,你只是停止。

這是一個簡單的 JavaScript(而不是 Java)解決方案:

let n = '11100';
n.length + n.replace(/0/g, '').length - 1;

只需多做一點工作,如果需要的話,這也可以正確處理前導零“0011100”。


查看完整回答
反對 回復 2023-09-20
?
拉風的咖菲貓

TA貢獻1995條經驗 獲得超2個贊

需要減去的次數就是 1 位的個數Integer.bitCount()。您需要除法的次數是最高有效位的位置,即Integer.SIZE(32,整數中的總位數)減去Integer.numberOfLeadingZeros()減一(您不需要除法1)。我假設對于零輸入,結果應該為零。所以我們有

int?numberOfOperations?=?integer?==?0???0?:?Integer.bitCount(integer)?+?
??Integer.SIZE?-?Integer.numberOfLeadingZeros(integer)?-?1;


查看完整回答
反對 回復 2023-09-20
?
Cats萌萌

TA貢獻1805條經驗 獲得超9個贊

根據給定的條件,如果數字是偶數,我們將其除以 2,這相當于刪除 LSB,同樣,如果數字是奇數,我們將減去 1 并將其設為偶數,這相當于取消設置設置位(更改 1)至 0)。分析上述過程我們可以說,所需的總步驟數將是(位數,即(log2(n)+1))和設置位數 - 1(最后的0不需要刪除)之和。

C++代碼:

result = __builtin_popcount(n) + log2(n) + 1 - 1;

 result =  __builtin_popcount(n) + log2(n);


查看完整回答
反對 回復 2023-09-20
  • 3 回答
  • 0 關注
  • 138 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號