Колькасць 1 біт


Узровень складанасці Лёгка
Часта пытаюцца ў Саман скрынка Cisco facebook Qualcomm
Біт Бітавая маніпуляцыя біты

Мы ўсе чулі пра Вага Хэмінга двайковага ліку. Вага Хэмінга - гэта колькасць усталяваных бітаў / 1 у двайковым ліку. У гэтай праблеме Колькасць 1 біт мы павінны знайсці ўдарную вагу дадзенага нумар.

Прыкладаў

Лік = 3

Бінарнае ўяўленне = 011

Вага Хэмінга = 2

Лік = 4

Бінарнае ўяўленне = 100

Вага Хэмінга = 1

Некалькі ўяўленняў пра малюнкі дапамогуць больш

Колькасць 1 біт

Зараз давайце разбярэмся, як гэта даведацца

Падыход - 1А

Грубая сіла

Падыход грубай сілы быў бы

  • Знайдзіце n% 2, каб даць нам біт у гэтай пазіцыі
  • Вылічыце n = n / 2, каб перайсці да наступнага біта

Прыклад

Лік = 5

Колькасць 1 біт

Давайце паглядзім на код.

Праграма JAVA 

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         ans=ans+(n%2);
         n=n/2;
     }
     return ans; 
    }
};

Праграма C ++

public class Solution { 
       // you need to treat n as an unsigned value 
       public int hammingWeight(int n) 
       { 
           int ans=0; 
           while(n!=0) 
           { 
               ans=ans+(n%2); 
               n=n/2; 
           } 
           return and; 
      } 
}

Складанасць часу = O (n)

Падыход - 1В

Грубая сіла АЛЕ разумнейшая!

Ну, цяпер у нас просты падыход. Давайце паглядзім больш з пункту гледжання біт-маніпуляцыі

Спачатку ўзмацніце нашу гульню некалькімі разумнымі ачкамі

  • Мы ведаем, што прынятае цэлае лік можа мець максімум 32 біты
  • a&1=1 1&0=0

Захоўваючы гэтыя рэчы, мы можам пракруціць 32 і выканаць аперацыю І, каб знайсці зададзеныя біты

Праграма JAVA для колькасці 1 біт

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;
    }
}

Праграма C ++ для колькасці 1 біт

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;    
    }
};

Складанасць часу = O (n)

Шмат падыходаў, якія мы сабралі да гэтага часу, лінейныя. Мы павінны, безумоўна, мець у сваім кацяняці адну разумную штуку для аптымізацыі нашай гульні. Такім чынам, гледзячы папярок, я трапіў на нешта залатое.

Падыход - 2

Алгарытм Брайана Кернігана

Перш чым атрымаць усе эрудытаваныя і алгарытмічныя, дазвольце мне правесці вас праз працэс

  • Мы разлічваем n-1
  • Мы і гэта з п. Н. Н & (п-1)
    • Такім чынам, усталяваны самы правы біт
  • Працягвайце паўтараць вышэйапісаныя дзеянні, пакуль у нас не атрымаецца 0

Няхай лік = 5

Бінарнае ўяўленне = 101

Працэс, праілюстраваны нумарам = 5
Працэс, праілюстраваны нумарам = 5

аптымізацыі

  • Алгарытм праходзіць столькі ітэрацый, колькі і зададзеных бітаў

Зазіраючы ў код

Праграма Java для колькасці 1 біт

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
}

Праграма C ++ для колькасці 1 біт

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
};

Аналіз складанасці часу

Кожнае цэлае лік мае log (n) біт, і ў горшым выпадку мы праходзім праз усе біты

Складанасць часу = Log (n)

Цяпер, калі мы паскараем, як мы можам прапусціць падыход, які прымае O (1)

Увядзенне

Падыход - 3

Выкарыстанне пашыраных аперацый

Давайце выкажам здагадку, што мы маем двайковы лік = 11010011

Мы выкарыстоўваем тут бітавыя маскі, а менавіта 0101,0011,00001111,00000000011111111 і 000000000000000001111111111111111 для выканання працэдуры, паказанай на малюнку.

 

Разлік вагі Хэмінга з выкарыстаннем Bitmask
Разлік вагі Хэмінга з выкарыстаннем Bitmask

Праграма JAVA для колькасці 1 біт

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    n = (n & 0x55555555) + (n >>  1 & 0x55555555); // put count of each  2 bits into those  2 bits 
    n = (n & 0x33333333) + (n >>  2 & 0x33333333); // put count of each  4 bits into those  4 bits 
    n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F); // put count of each  8 bits into those  8 bits 
    n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits 
    n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits 
    return n;
    }
}

Часавая складанасць вышэйзгаданага падыходу і касмічная складанасць у канчатковым выніку складаюцца як O (1).

Хачу ведаць не толькі бінарны файл. Наладзіць!

Спасылкі