Differenzzulage, hat sich ergeben:
A.- Die Beamten der Stadtpolizei Zürich werden grundsätzlich nach der städtischen Besoldungsverordnung vom 15. Juli 1993 (mit seitherigen Änderungen) besoldet. Seit 1972 wurde ihnen zusätzlich zur Besoldung eine sogenannte Differenzzulage ausgerichtet, um die Besoldungsdifferenzen gegenüber den entsprechenden Funktionen der Kantonspolizei zu reduzieren. Diese Zulage beruhte auf besonderen Beschlüssen und wurde 1988 letztmals angepasst. Am 1. Oktober 1997 beschloss der Gemeinderat (Parlament) der Stadt Zürich, den Stadtrat zu ermächtigen, die Differenzzulage für das Jahr 1998 festzulegen; zugleich hob er seine Beschlüsse über die Differenzzulage für das Jahr 1998 auf den Zeitpunkt auf, an welchem die vom Stadtrat festgelegten neuen Ansätze in Kraft treten. Gestützt darauf legte der Stadtrat am 5. November 1997 die Differenzzulage für das Jahr 1998 fest. Dabei wurden für die meisten Angehörigen der Stadtpolizei die Zulagen im Umfang von maximal Fr. --.-- gekürzt.
Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie einzelne Beamtinnen und Beamte erhoben gegen den Beschluss des Gemeinderats vom 1. Oktober 1997 sowie gegen den Beschluss des Stadtrats vom 5. November 1997 Beschwerde bzw. Rekurs an den Bezirksrat Zürich, der die Rechtsmittel am 23. April 1998 abwies. Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie einzelne Beamtinnen und Beamte erhoben gegen den Entscheid betreffend den Gemeinderatsbeschluss Beschwerde an den Regierungsrat und zudem gegen beide Entscheide Beschwerde an das Verwaltungsgericht des Kantons Zürich. Am 7. September 1998 trat das Verwaltungsgericht auf die Beschwerde betreffend den Gemeinderatsbeschluss nicht ein und sistierte die Beschwerde betreffend den Stadtratsbeschluss bis zum Entscheid des Regierungrates im Rechtsmittelverfahren gegen den Gemeinderatsbeschluss. Der Regierungsrat wies die Beschwerde betreffend den Gemeinderatsbeschluss am 23. Dezember 1998 ab. Das Verwaltungsgericht nahm daraufhin das Verfahren betreffend den Stadtratsbeschluss wieder auf und wies die Beschwerde am 23. Juni 1999 ab.
B.- Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie sieben Beamtinnen und Beamte erheben staatsrechtliche Beschwerde mit dem Antrag, das Urteil des Verwaltungsgerichts vom 23. Juni 1999 sowie die Beschlüsse vom 1. Oktober 1997 und vom 5. November 1997 seien aufzuheben. Sie rügen eine Verletzung von Art. 4 aBV und von Art. 6 Ziff. 1 EMRK.
C.- Der Stadtrat von Zürich beantragt im Auftrag des Gemeinderates Abweisung der staatsrechtlichen Beschwerde. Die Direktion der Justiz und des Innern des Kantons Zürich im Namen des Regierungsrats sowie das Verwaltungsgericht beantragen, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne.
D.- Mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 12. Oktober 1999 wurde der Beschwerde aufschiebende Wirkung beigelegt.

Das Bundesgericht zieht in Erwägung:
1.- a) Die staatsrechtliche Beschwerde gegen den kantonal letztinstanzlichen Endentscheid, gegen den auch kein anderes bundesrechtliches Rechtsmittel gegeben ist, ist grundsätzlich zulässig (Art. 84 Abs. 2, Art. 86 Abs. 1 sowie Art. 87 BV). Die beschwerdeführenden Einzelpersonen sind als betroffene Beamtinnen und Beamte befugt, mit staatsrechtlicher Beschwerde zu rügen, ihre Besoldung werde willkürlich, rechtsungleich oder in einer gegen Treu und Glauben verstossenden Weise festgesetzt (Art. 88 OG; <ref-ruling>, nicht publizierte E. 1b). Desgleichen sind die beschwerdeführenden Verbände zur Beschwerde legitimiert (<ref-ruling> E. 1b S. 75 mit Hinweisen).
b) Die staatsrechtliche Beschwerde kann sich indessen nur gegen den letztinstanzlichen kantonalen Entscheid richten. Das ist vorliegend das Urteil des Verwaltungsgerichts vom 23. Juni 1999. Soweit in der Beschwerde auch die Aufhebung der Beschlüsse vom 1. Oktober 1997 und vom 5. November 1997 beantragt wird, kann darauf nicht eingetreten werden. Nach einer allfälligen Aufhebung des verwaltungsgerichtlichen Urteils hätte freilich das Verwaltungsgericht auch über den seinem Urteil zugrunde liegenden Stadtratsbeschluss vom 5. November 1997 neu zu befinden. Demgegenüber bildete der Beschluss des Gemeinderates vom 1. Oktober 1997 nicht Gegenstand des angefochtenen Verwaltungsgerichtsurteils. Er wurde letztinstanzlich durch den Nichteintretensentscheid des Verwaltungsgerichts vom 7. September 1998 und den Regierungsratsentscheid vom 23. Dezember 1998 beurteilt, ohne dass die Beschwerdeführer diese Entscheide angefochten hätten. Entgegen der Ansicht der Beschwerdeführer handelt es sich dabei nicht um einen Zwischenentscheid, der mit dem Endentscheid vom 23. Juni 1999 angefochten werden könnte. Vielmehr betraf das Verfahren vor dem Regierungsrat einen anderen Gegenstand als dasjenige vor dem Verwaltungsgericht. Der Gemeinderatsbeschluss vom 1. Oktober 1997 kann somit im vorliegenden Verfahren nur bezogen auf den konkreten Anwendungsfall auf seine Verfassungsmässigkeit hin überprüft werden (<ref-ruling> E. 1f S. 309).
2.- Die Beschwerdeführer erblicken eine Verletzung von Art. 6 Ziff. 1 EMRK im Umstand, dass das Verwaltungsgericht trotz ihrem ausdrücklichen Antrag keine öffentliche Verhandlung durchgeführt habe.
a) Gemäss Art. 6 Ziff. 1 EMRK hat vorbehältlich bestimmter Ausnahmen jedermann Anspruch darauf, dass über zivilrechtliche Ansprüche und Verpflichtungen in öffentlicher Verhandlung entschieden wird. Es ist somit zu prüfen, ob ein zivilrechtlicher Anspruch vorliegt. Gemäss ständiger Praxis beurteilt sich diese Frage nach dem Konventionsrecht unabhängig von der landesrechtlichen Qualifikation (<ref-ruling> E. 7a S. 215 f.; <ref-ruling> E. 4b/aa S. 379 mit Hinweis).
b) In Frage stehen Besoldungsansprüche von Beamten. Die Praxis der Konventionsorgane bezüglich Streitigkeiten aus dem öffentlichen Dienstverhältnis entwickelte sich nicht einheitlich. Nach der bisherigen Rechtsprechung wurden solche Streitigkeiten dem Anwendungsbereich von Art. 6 Ziff. 1 EMRK weitgehend entzogen. Das galt namentlich für die Begründung des Dienstverhältnisses, für Lohneinstufungen und Beförderungen sowie für die Beendigung des Dienstverhältnisses. Demgegenüber wurden bestimmte Streitigkeiten über vermögensrechtliche Ansprüche aus dem Dienstverhältnis als zivilrechtlich betrachtet, so namentlich sozialversicherungsrechtliche Ansprüche sowie andere rein oder überwiegend vermögensrechtliche Ansprüche (vgl. Darstellung der Rechtsprechung in <ref-ruling> E. 4 S. 319 f. mit zahlreichen Hinweisen). In einem Urteil vom 8. Dezember 1999 i.S. Pellegrin c. Frankreich erwog nun jedoch der Europäische Gerichtshof für Menschenrechte, diese bisherige Rechtsprechung schaffe Rechtsunsicherheiten, da auch diejenigen dienstrechtlichen Angelegenheiten, die in der bisherigen Rechtsprechung als nicht pekuniär beurteilt wurden, regelmässig vermögensmässige Auswirkungen hätten. Der Gerichtshof suchte daher für die Abgrenzung des Anwendungsbereichs von Art. 6 EMRK nach einem neuen Kriterium, welches nicht auf die Natur der Streitsache, sondern auf die Natur der ausgeübten Funktion abstelle. Massgebendes Kriterium sei, ob der Beamte eine Aufgabe im allgemeinen Interesse wahrnehme bzw. an der Ausübung der öffentlichen Gewalt teilhabe. Die Inhaber solcher Ämter hätten einen Teil der staatlichen Souveränität inne, weshalb der Staat ein legitimes Interesse an einem besonderen Vertrauens- und Loyalitätsverhältnis habe. Streitigkeiten von öffentlichen Beamten, die derart an der Ausübung der öffentlichen Gewalt teilhätten, wie namentlich Angehörige der Streitkräfte und der Polizei, unterstünden demzufolge ausser in Bezug auf pensionsrechtliche Ansprüche nicht den Garantien von Art. 6 Ziff. 1 EMRK, während öffentliche Angestellte, die andere Funktionen wahrnehmen, sich auf diese Bestimmung berufen könnten (§§ 60-67 des genannten Entscheids). Diese Rechtsprechung, die ausdrücklich als Abkehr von der bisherigen Praxis deklariert ist, schafft zwar ihrerseits neue Abgrenzungsprobleme. Klar ist indessen, dass sich Polizeibeamte nach dieser neuen Rechtsprechung bezüglich ihrer Besoldungsansprüche nicht auf Art. 6 Ziff. 1 EMRK berufen können. Die Rüge der Verletzung von Art. 6 Ziff. 1 EMRK erweist sich daher von vornherein als unbegründet.
3.- Die Beschwerdeführer rügen eine Verletzung des Anspruchs auf rechtliches Gehör. Sie hatten im Verfahren vor Verwaltungsgericht eine Expertise beantragt, um das Ausmass der Lohndifferenzen zwischen der Stadtpolizei und der Kantonspolizei abzuklären. Das Verwaltungsgericht erwog, welche Faktoren der Stadtrat im Rahmen seines Ermessensspielraumes in den Vergleich miteinbeziehen bzw. weglassen dürfe, betreffe nicht den nötigenfalls durch Expertise zu klärenden Sachverhalt, sondern sei eine Rechtsfrage. Der Stadtrat räume gewisse Ungenauigkeiten der Vergleichsgrundlagen ohnehin ein. Es seien nicht diese Ungenauigkeiten zu qualifizieren, sondern es sei darüber zu entscheiden, ob der Stadtrat auf der Grundlage dieses anerkanntermassen ungenau ermittelten Sachverhalts die Differenzzulage habe festsetzen dürfen.
a) Der Anspruch auf rechtliches Gehör, der nun ausdrücklich in Art. 29 Abs. 2 BV verankert ist, umfasst das Recht, Beweisanträge zu stellen und die Pflicht der Behörde zur Beweisabnahme. Diese Pflicht gilt aber nur für Beweisanträge, welche geeignet sind, rechtserhebliche Sachverhaltsfragen zu beweisen. Gelangt das Gericht zur begründeten Überzeugung, der Sachverhalt, den eine Partei beweisen will, sei nicht rechtserheblich, kann auf die Abnahme eines beantragten Beweismittels verzichtet werden (<ref-ruling> E. 4a S. 469; <ref-ruling> E. 1d S. 162, je mit Hinweisen).
b) Die Beschwerdeführer wollten mit der beantragten Expertise feststellen lassen, wie gross die Differenz zwischen den Besoldungen der Stadt- und der Kantonspolizei sei. Dieses Beweismittel wäre nur rechtserheblich, wenn sich aus dem Ausmass der festgestellten Lohndifferenz bestimmte Rechtsfolgen ableiten liessen. Das wäre der Fall, wenn es eine Rechtsnorm gäbe, welche festlegt, dass die Löhne der Stadtpolizei in einem bestimmten Verhältnis zu denjenigen der Kantonspolizei liegen müssen. Dass es eine solche Norm gebe, wird indessen von den Beschwerdeführern nicht geltend gemacht. Grundsätzlich steht den zuständigen Behörden ein erhebliches Ermessen bei der Festsetzung der Beamtenlöhne zu (<ref-ruling> E. 6b S. 8 mit Hinweisen). Insbesondere ist ein Gemeinwesen nicht verpflichtet, seinen Beamten gleiche Löhne zu bezahlen wie ein anderes Gemeinwesen (<ref-ruling> E. 3c S. 51 f.). Die mit der Differenzzulage beabsichtigte Annäherung der Besoldungen zwischen den beiden Polizeikorps ist lohnpolitisch motiviert, aber nicht gesetzlich festgelegt. Der Gemeinderatsbeschluss vom 1. Oktober 1997 ermächtigt den Stadtrat, die Differenzzulage festzulegen, enthält aber keine näheren Kriterien für die Ausgestaltung dieser Zulage. Wohl ergibt sich aus dem Sinn und Geist des Beschlusses, dass mit der Zulage eine Anpassung der Besoldungen der Stadtpolizei an jene der Kantonspolizei erfolgen soll, doch bedeutet das nicht zwingend, dass der Gemeinderat den Stadtrat verpflichten wollte, die Löhne genau gleich hoch festzulegen wie diejenigen des Kantons. Schon in dem von den Beschwerdeführern zitierten Beschluss des Stadtrates vom 4. September 1987, mit welchem eine Erhöhung der Differenzzulage beantragt worden war, wurde nicht eine völlige Angleichung, sondern bloss eine Annäherung der Besoldungen beabsichtigt. Auch in den Weisungen des Stadtrates an den Gemeinderat vom 16. Juli 1997, mit welchen der Stadtrat die Ermächtigung beantragte, die Differenzzulage festzusetzen, ist nicht von einer völligen Angleichung die Rede, sondern einerseits von Gleichbehandlung mit dem in Anlehnung an den Kanton besoldeten städtischen Personal, andererseits vom Bedürfnis, rasch und flexibel reagieren zu können, um allfällige Sparpotentiale zu realisieren. Unter diesen Umständen ist ein genauer Vergleich der Besoldungen zwischen Stadt- und Kantonspolizei von vornherein unerheblich. Selbst wenn die von den Beschwerdeführern behaupteten Zahlen zutreffen sollten, ergäbe sich daraus kein Rechtsanspruch der Stadtpolizeibeamten auf eine höhere Differenzzulage. Somit durfte das Verwaltungsgericht die beantragte Expertise als nicht rechtserheblich beurteilen. Die Rüge, der Anspruch auf rechtliches Gehör sei verletzt, erweist sich daher als unbegründet.
4.- Die Beschwerdeführer beanstanden eine Verletzung von Treu und Glauben und einen Verstoss gegen das Legalitätsprinzip. Die Differenzzulage stehe jedem Angehörigen der Stadtpolizei individuell zu und könne nicht nachträglich entzogen werden. Zumindest hätte der erhebliche Vermögensentzug eine ausdrückliche Beschlussfassung durch den Gemeinderat erfordert. Der Gemeinderatsbeschluss vom 1. Oktober 1997 und der Stadtratsbeschluss vom 5. November 1997 bildeten keine genügende gesetzliche Grundlage.
a) Das öffentliche Dienstrecht wird durch die jeweilige Gesetzgebung bestimmt; es macht deshalb, auch was die vermögensrechtliche Seite betrifft, grundsätzlich die Entwicklung mit, welche die Gesetzgebung erfährt. Nach der Rechtsprechung des Bundesgerichts kommt den finanziellen Ansprüchen der Beamten in der Regel nicht der Charakter wohlerworbener Rechte zu, sofern nicht das Gesetz die entsprechenden Beziehungen ein für alle Mal festlegt und von den Einwirkungen der gesetzlichen Entwicklung ausnimmt oder bestimmte, mit einem einzelnen Anstellungsverhältnis verbundene Zusicherungen abgegeben worden sind. Soweit die vermögensrechtlichen Ansprüche keine wohlerworbenen Rechte darstellen, sind sie gegenüber Anordnungen des Gesetzgebers nur nach Massgabe des Willkürverbots und des Gebots der Rechtsgleichheit geschützt; der Beamte kann sich aufgrund von Art. 4 aBV bzw. Art. 8 Abs. 1 und Art. 9 BV (Treu und Glauben) dagegen zur Wehr setzen, dass solche Ansprüche willkürlich abgeändert, nachträglich entzogen oder im Wert herabgesetzt werden und dass Eingriffe ohne besondere Rechtfertigung einseitig zu Lasten einzelner Berechtigter oder bestimmter Gruppen erfolgen (<ref-ruling> E. 5b S. 255 f.; Pra 1997 1 E. 3b; Pra 1998 31 S. 227 E. 3b, je mit Hinweisen).
b) Die Beschwerdeführer machen nicht geltend, die Höhe der Differenzzulage sei gesetzlich ein für alle Mal als unveränderlich festgelegt oder es seien den einzelnen Beamten entsprechende individuelle Zusicherungen abgegeben worden. Die Höhe der Zulage stellt kein unabänderliches wohlerworbenes Recht dar. Der blosse Umstand, dass die Zulage aufgrund der jeweils massgebenden gesetzlichen Regelung den einzelnen Beamten je individuell zusteht oder dass diese in Erwartung einer Weiterführung der bisherigen Regelung gewisse Dispositionen getroffen haben mögen, ändert daran nichts (vgl. Pra 1997 1 E. 3c und 4c).
c) Die Beschwerdeführer machen auch nicht geltend, die Reduktion der Differenzzulage habe in rechtsungleicher oder sachlich unhaltbarer Weise bestimmte Gruppen von Beamten betroffen. Die Differenzzulage ist eine Leistung, die nicht an alle städtischen Bediensteten ausbezahlt wird. Es kann grundsätzlich nicht unzulässig sein, eine Zulage, die nur an bestimmte Kategorien ausgerichtet wird, zu kürzen.
d) Das Legalitätsprinzip besagt, dass ein staatlicher Akt sich auf eine materiellgesetzliche Grundlage stützen muss, die hinreichend bestimmt ist (materielles Legalitätsprinzip, Erfordernis eines materiellen Gesetzes); zudem muss diese Grundlage vom staatsrechtlich hierfür zuständigen Organ erlassen worden sein (formelles Legalitätsprinzip, Erfordernis eines formellen Gesetzes bzw. einer verfassungsrechtlich zulässigen Kompetenzzuweisung an ein anderes Organ als den formellen Gesetzgeber; vgl. <ref-ruling> E. 2b S. 3 f. mit Hinweisen; Hansjörg Seiler, Rechtsetzung, Generell-Abstraktheit und staatliche Kompetenzordnung, Festschrift Hangartner, St. Gallen 1998, S. 343 ff., 355). Soweit die Beschwerdeführer vorbringen wollen, die Festlegung der Differenzzulage verstosse gegen das formelle Legalitätsprinzip, so hätte eine solche Kritik in erster Linie mit einer Beschwerde wegen Verletzung des Gewaltenteilungsprinzips gegen den Gemeinderatsbeschluss vom 1. Oktober 1997 bzw. gegen den diesen Beschluss schützenden Regierungsratsbeschluss vom 23. Dezember 1998 vorgebracht werden müssen. Die Zulässigkeit dieser Kompetenzdelegation steht im vorliegenden Verfahren nur mehr vorfrageweise zur Diskussion (E. 1b). Für ihre Beurteilung ist unerheblich, ob der Beschluss des Stadtrates vom 5. November 1997 als Allgemeinverfügung oder als Rechtssatz zu qualifizieren ist. Unter Gewaltenteilungsaspekten stellt sich ohnehin die Frage, ob der Gemeinderat die Kompetenz zur Festsetzung der Differenzzulage dem Stadtrat übertragen durfte. Dies ist zu trennen von der Frage, in welcher Form der Stadtrat von seiner Kompetenz Gebrauch macht.
e) Welche Behörde wofür zuständig ist, ergibt sich in erster Linie aus dem kantonalen Staatsrecht. Bundesrechtlich ist die Delegation von Rechtsetzungsbefugnissen auch vom kantonalen (oder kommunalen) Gesetzgeber an eine Verwaltungsbehörde zulässig, wenn sie in einem formellen Gesetz enthalten ist, nicht durch das kantonale (bzw. kommunale) Recht ausgeschlossen wird, sich auf ein bestimmtes Gebiet beschränkt und das Gesetz die Grundzüge der Regelung selbst enthält, soweit sie die Rechtsstellung des Bürgers schwerwiegend berührt (<ref-ruling> E. 3b S. 247 f., 305 E. 2b S. 310 f.).
Die Beschwerdeführer führen nicht aus, gegen welche Bestimmungen des kantonalen oder kommunalen Rechts die im Gemeinderatsbeschluss vom 1. Oktober 1997 enthaltene Ermächtigung an den Stadtrat verstossen soll. Dieser Beschluss unterstand dem fakultativen Referendum. Zudem wurde gemäss den Ausführungen des Regierungsrates in seinem Beschwerdeentscheid vom 23. Dezember 1998 die Differenzzulage ursprünglich einzig durch Beschluss des Stadtrates eingeführt. Der blosse Umstand, dass der Gemeinderat 1987 die Höhe der Differenzzulage selber festlegte, schliesst nicht aus, dass er später diese Kompetenz wieder an den Stadtrat delegiert. Verfassungsrechtlich wird jedenfalls nicht verlangt, dass die genaue Höhe der Beamtenlöhne durch den formellen Gesetzgeber oder durch das Parlament festgesetzt wird (<ref-ruling> E. 3 S. 5; <ref-ruling> E. 3; <ref-ruling> E. 2 S. 109 f.).
f) Die Verletzung des materiellen Legalitätsprinzips kann - abgesehen vom Abgaberecht und vom Strafrecht - nicht als Verletzung eines selbständigen verfassungsmässigen Rechts, sondern nur im Zusammenhang mit einem speziellen Grundrecht, dem Willkürverbot oder der Rechtsgleichheit geltend gemacht werden (<ref-ruling> E. 2b S. 4; <ref-ruling> E. 3a S. 25; je mit Hinweisen). Insoweit nach diesen Grundsätzen überhaupt auf die Rüge einer ungenügend bestimmten gesetzlichen Grundlage eingetreten werden kann, erweist sie sich als offensichtlich unbegründet. Der Stadtratsbeschluss vom 5. November 1997 erfüllt die Anforderungen an die Bestimmtheit einer gesetzlichen Grundlage ohne weiteres. Er legt für jede Funktion die Höhe der für das Jahr 1998 geltenden Differenzzulage frankenmässig fest. Es ist nicht ersichtlich, wie eine gesetzliche Grundlage noch bestimmter gefasst werden könnte.
5.- Die Beschwerdeführer rügen eine willkürliche Anwendung von Art. 4 Abs. 4 der städtischen Besoldungsverordnung durch das Verwaltungsgericht. Nach dieser Bestimmung könne die Besoldung pro Amtsperiode höchstens für ein Jahr gekürzt werden und die gesamte Besoldungseinbusse dürfe 5,1 % der Jahresbesoldung nicht übersteigen. Den Polizeibeamten sei, wie dem gesamten städtischen Personal, bereits im Jahre 1995 die Besoldung gekürzt worden. Die zusätzliche Kürzung der Differenzzulage verstosse gegen Art. 4 Abs. 4 der Besoldungsverordnung. Zudem basiere sie auf einer willkürlichen Bestätigung der stadträtlichen Berechnungen.
a) Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst dann, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt sodann nur vor, wenn nicht bloss die Begründung eines Entscheides, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 2a S. 168; <ref-ruling> E. 4a S. 5, je mit Hinweisen).
b) Art. 4 Abs. 4 der Besoldungsverordnung (in der Fassung vom 5. Oktober 1994) lautet wie folgt:
"Der Gemeinderat ist ermächtigt, die Besoldungsansätze gemäss Abs. 1 aus triftigen finanziellen Gründen vorübergehend zu reduzieren, jedoch nur zeitlich und umfangmässig beschränkt. Während einer Amtsdauer darf eine Reduktion höchstens für ein Jahr beschlossen werden, und die gesamte Besoldungseinbusse darf 5,1 % der Jahresbesoldung, entsprechend 2/3 des 13. Monatslohnes, nicht übersteigen. "
Das Verwaltungsgericht erwog, dieser Absatz beziehe sich auf die Besoldungsansätze gemäss Abs. 1 von Art. 4, das heisst auf die Jahresbesoldung nach der im Anhang der Besoldungsverordnung enthaltenen Skala der Besoldungsklassen. Zu dieser gehöre die Differenzzulage nicht, da sie neben und zusätzlich zu den in der Besoldungsverordnung vorgesehenen Entschädigung ausgerichtet werden.
c) Diese Erwägung kann nicht als willkürlich bezeichnet werden. Sie entspricht im Gegenteil dem klaren
Wortlaut: Art. 4 Abs. 4 der Besoldungsverordnung verweist auf Abs. 1, welcher lautet:
"Die Mindest- und Höchstbeträge der Jahresbesoldungen, einschliesslich 13. Monatslohn, richten sich bei voller Beschäftigung nach der im Anhang enthaltenen Skala der Besoldungsklassen. Jede Besoldungsklasse wird in 9 Stufen eingeteilt. Die Differenz zwischen den Stufen entspricht einem Achtel des Unterschiedes zwischen Mindest- und Höchstbetrag. "
Im Anhang, auf den Abs. 1 verweist, werden sodann für jede Besoldungsklasse ein Minimum und ein Maximum festgelegt. Die Beschwerdeführer bestreiten nicht, dass die Differenzzulage in diesen Besoldungsansätzen nicht inbegriffen ist, sondern zusätzlich dazu ausbezahlt wird. Indem Art. 4 Abs. 1 auf die Ansätze gemäss Anhang und Abs. 4 seinerseits auf Abs. 1 verweist, bezieht sich das in diesem Absatz enthaltene Verbot, die Besoldung mehr als insgesamt einmal pro Amtsdauer um 5,1 % einer Jahresbesoldung zu kürzen, nur auf die Besoldungen gemäss Anhang und mithin nicht auf die Differenzzulage. Zumindest ist die entsprechende Auslegung des Verwaltungsgerichts nicht offensichtlich unhaltbar.
d) Dass die stadträtlichen Vergleichsberechnungen zwischen den Besoldungen der Stadt- und der Kantonspolizei fehlerhaft gewesen sein sollen, wäre nur erheblich, wenn es einen Rechtsanspruch auf ein bestimmtes Verhältnis zwischen diesen beiden Besoldungen gäbe, was aber nach dem Gesagten (E. 3b) nicht der Fall ist. Es braucht daher nicht im Einzelnen geprüft zu werden, ob die Besoldungsvergleiche zutreffend waren.
6.- Die staatsrechtliche Beschwerde erweist sich daher als unbegründet, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 156 Abs. 1 und 7 OG). Der obsiegenden Stadt Zürich wird praxisgemäss keine Parteientschädigung zugesprochen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Die Gerichtsgebühr von Fr. 25'000. -- wird den
Beschwerdeführern auferlegt.
3.- Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat und dem Stadtrat von Zürich sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, schriftlich mitgeteilt.
_
Lausanne, 7. Februar 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: