Aller au contenu

Nombre de bits égaux à 1

Le cadre

L'écriture binaire d'un entier est composée de 0 et de 1.

Par exemple, en binaire, l'entier \(13 = 1×8 + 1×4 + 0×2 + 1×1\) s'écrit 1101.

On peut dire qu'il y a trois 1 dans son écriture binaire.

Objectif et méthode

On souhaite coder une fonction récursive nb_bits_1 qui prend en argument un entier positif n et qui renvoie le nombre de bits égaux à 1 dans l'écriture binaire de n.

Pour cela, on peut remarquer que :

  • si n < 2 (les cas n=0 et n=1), alors la réponse est n
  • sinon, la réponse se calcule facilement à l'aide de n // 2 et n % 2

Schématiquement,

  • le nombre de bits égaux à 1 dans abcd_efgh_ijkl est égal
    • au nombre de bits égaux à 1 dans abc_defg_hijk
    • plus un si le bit l vaut 1.
  • Pour obtenir abc_defg_hijk, il suffit de calculer le quotient dans une division par deux.
  • Pour obtenir l, il suffit de calculer le reste.

Exemple : Bits de 13

  • Si n = 13, alors nb_bits_1(n) est égal à
    • nb_bits_1(6) + 1 = 2 + 1 = 1
    • avec
      • 6 : le quotient 13 // 2
      • 1 : le reste 13 % 2
  • Pour n = 6, on a obtenu nb_bits_1(n) est égal à
    • nb_bits_1(3) + 0 = 2 + 0 = 2
    • avec
      • 3 : le quotient 6 // 2
      • 0 : le reste 6 % 2
  • Pour n = 3, on a obtenu nb_bits_1(n) est égal à
    • nb_bits_1(1) + 1 = 1 + 1 = 2
    • avec
      • 1 : le quotient 3 // 2
      • 1 : le reste 3 % 2

Exercice

Coder une fonction récursive nb_bits_1 qui prend en paramètre un entier positif n et qui renvoie le nombre de bits égaux à 1 de n.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013x,5/f.qr;nb _o=ylae%êpcwgu)vdV4613kRméhtsP(S+à2Cè-i:E050D0t0O0s0Z0r0P0m0x0r0s0P0P0p010O0Z0w010406050P0A0L0L0s0i0q040S0o0r0A0_0o0k0m020s0L0w0j0m0K0t130i0h0A0t0P050e101214160~0w04051B1u1E0e1B0~0D0Z0C0.0:0=0@0N0Z0z0N0r1S0N0O0|050)0l0r0t1N0;0?011R1T1V1T0O1#1%1Z0O0i1C0O0N1)1P010f0+0t0k1h0t010.190P0w0s0k0@0V1Z292b1}1+201%230L25040a0m0Q0i0o0w0o0P0Z1c1e0%270i0i0t0x2z1u2g0k1C0e1{2L1^1`1_1!0D2i0@1V0k222w1Z1K1M0/1*2V0Z2X0k0o2#1Z0w2E1C2J2L2?0 2a1e2%1~2,0i130r0|0H2I2`0}2_2h2|1+2~300|0V342b362J2U013b0s31040I3f2K0~3i390@3l3n0F3q3h2`3j3w0|0d3z3s3B3u3k0o2 3m0|0G3z1F2;1u2#2O0D1`2T3J0x2-2o0$1L1C2:0t2=353Q3!0%3,381O1+0J0|0%0f3Q3t3?0@0y0|0m3|3I3~3k0f0|0k0l0n0l2y0P0n331v3-3}2(010{040R433=4k0k484p2{454m0B0!3G374v4k40040m4G424h3g4B3j0P0D0|014Q1m0k0C0o0Z1(1%0m2v0Z0D0-0%0-4c0O4%4X00220_0t0i4Z2w2y0Z0f0m4s4Q3G4H424j1~3^044_3z50444r4t4J2K574q1~0o0|020r0O0j564L3J0L0Z3d4u3j4m4z5b0}4 4 5n45532E0O0A0i0k5m513a5a2?065z5J0@530t0,0t5s3J5u4~5y4G5A4k5C0(5F5H5w5d4C2}484a4*4e4g2^5P4l0|4o5w5#5.045*2?5,3j5g040e0e5I581~5p5r5|5^4x685e1+640T6g5-1+4m5{5@695K5 6l630|0u6u5o5q043e6d6r0@6f5w0~0e3/3+3R6L0e3U1u0O3W6Q2R2M0s1$6N3U1A3;6m0@2E0L0n0f0s0J0t0n0N0I0|1m1o1q1s0m5v2^1H362#3j0s0D0L1d4^1d0m2*0f641A7072742z0Y0_0O1?040E140Z2b0O1(0s0C2F426K042#730D1u7v1F6~1L3j1-1U1W1Y6#3j2k22240|2q0S0x0i0`0O2r0q1{1d3Q3*6#2@3-7B5^533`5V454E4I6q6h3v475 5:4d4f7-4k6o7|5~604i6E5_044y4A5^7/4H7 1+4N4P4R224U4W0m4Y4!4$0m4(0m5;8n4-4/4W4=2v2x0_4`4|015Y5!7*0|555+5}6s813g623J645i5k6y456b6B8b6F0|6{355N5Z8M5B0|5D5)8R596t6H5O835R5T8V848Y3g8!5Z8I3v0|0h8?4m0c8+5~0i936i0|0p963v0l3_1L7y905`8?4s8-7;6$84928H5^8T6C9l5t0|0B8C5y8|015%5E5G9a3k5/4b7`5?827=846p9K9m9j8 6D9L6G619z6j9E9j956H7A3#2L7#3T3(6!0W4.0P7V0A1e0l760i0M0f1%0b1(6^8n001b0+0Z0P4;7u9%7x2-9$3:8j3L0P1q00760P0o0A0N0*7p0m0o0l7p0k0Z4=4Y1q0o4:0k7V0 1^1d0z040(2IaC0kaE8j1(2E9/1(0Da02X0m0L0v2n8n1La30Z768t0X2E0g7C6I6Z0$0(0*0,3j0D2b0z4;0|3s111o167l7T7o1(7p0x0Nas6^0c8j0M0za%1n4/4Z1a0-0t0f200x0s0x5U1va{1y7D2$457G1/1X2f837M2m2o7Q7S7U7W7Y8K2K1D3S6|2^7)8:3_bh8?7/9i7@499H4+7{9S9m7~bZ3C5L9O9u858^3r9z895!b$3J8d044Q014S8h4X1(8l4,4)4d8r8j4.az8u4?8x4_4{b^9x9z538G9V5^9jbH4F9W5h5j5l9p839r9g04b,5x8#cd8(5(9Dcp9Lcicc8EaF8=b;4w8X9x8/cC8~9E6499cB9Pb(8Lcl04020z5kcY8QcS3j8T9J8_8#8$8,9!cg83cQ9YcU5ccW1g1icoc:9Lc)cL8acF8)cAc}cT7^bW5=cs9N4KchcOcI7}9vcP0|6kc%3J9Z4A6J9%6M2La,1B0#1ebh0faG6}0~0A0r361V1C6K7F1Wbv7J9zcDdl458OcZ0jc#c|35c-6a6Ac*bIdpab0D0Mbk4Y1%c04+c2057v5*7vc20H0m0ia?0m7s0i0-0:8n2t2y0tb7bm0m1q0Zd^0t0C4Waz0m0UaLaXeba48v148r0A0b0g0m0W0(an2u0Md_2z0m1s7V0M0r0M2naz0*2E4?5Feg2:0obm0=0t5Fb70D1d0x50aIaE1^0X1t1veW4Fd_0w4#0ta)0edF0~dFd/3#dI1.7IbxcN9kdVc_1h1j9Ec 5|d#3+ao0wbb0m9;eV2taJaF0O0Y0r0o0z0Z6^0Y4*0Y0Ufl2yaHfbaK0(e94T4Vb10ieZd^0se)0%eE7V4Y4*c2b~0m6+0Z6Xd.d:aa3+e,e.1udC366Oa.0+0PfX0%0)f!04.